[자료구조] 스택 - 키보드 Backspace / 괄호문법검사기

스쿼드 숙제!

 

키보드 Backspace 기능 구현하기

• input_string = ‘123//45/6789///’
• /를 만나면 앞의 값을 삭제해라
• 맨앞에 /를 만나면 어떻게 처리할지 생각해보기
• answer = '146'

열심히 생각해서 만든 코드

def backspace_string(input_string):   # 함수정의(문자열받기)
    
    stack = []                        # 변수선언 stack = 빈리스트
    for i in input_string:            # 문자열 돌면서 각요소 i에 할당
        if i == '/':                  # i가 /인 경우 :
            if stack != []:           # [stack]이 비어있지 않으면
                stack.pop()           # 마지막꺼 꺼내서 버림
            else:                     # [stack]이 비어있는데 /를 만나면
                pass                  # /는 아무 효과없이 지나감
        else:                         # i가 /가 아닐 경우 :
            stack.append(i)           # i를 [stack]에 추가함
            
    answer = ""                       # 변수선언 answer = 빈문자열
    for j in stack:                   # [stack] 돌면서 각요소 j에 할당
        answer += j                   # j를 그대로 answer에 추가함
    
    return answer                     # answer 반환

print(backspace_string("123//45/6789///"))               # 146

 

근데 굳이 저렇게 빈문자열 만들어서 일일이 추가해줄 필요없이 join() 함수를 쓰면 공백을 기준으로 엄청 간단하고 쉽게 문자를 이어줄 수 있다... ㅜ

    return "".join(stack)

 

그리고 엄청 멋진것도 있다!!

if문은 조건이 true일 경우 실행되기 때문에 if stack: 이라고만 해도 의미가 있다.

stack에 하나라도 들어있을 경우, true 이므로 pop이 실행되고

stack이 비어있을 경우([]), false 이므로 pop이 실행되지 않는다.

        if i == "/":
            if stack:
                stack.pop()
        else:
            stack.append(i)

 

결과

def backspace_string(input_string):
    stack = []
    for i in input_string:
        if i == "/":
            if stack:
                stack.pop()
        else:
            stack.append(i)
    return "".join(stack)

print(backspace_string("123//45/6789///"))  # 146
print(backspace_string("///123//45/6789///"))  # 146

---

괄호 문법 검사 기능 구현하기

• bracket1: [[[[]]]][] → answer ‘YES’
• bracket2: [[[[[[[[[[[[[[[[]] → answer ‘NO’
• 맨앞에 ]를 만나면 어떻게 처리할지 생각해보기

열심히 생각해서 만든 코드

def is_bracket(b):              # 함수선언, 괄호들로 이루어진 b 받아옴
    stack = []                  # 변수 선언, 빈 리스트 stack
    for i in b:                 # b를 하나씩 돌아서 i에 할당
        if i == '[':            # i 가 열린괄호일 경우
            stack.append(i)     # stack에 i 추가
        elif i == ']':          # i 가 닫힌괄호일 경우
            if stack != []:     # stack이 빈 리스트가 아니면
                stack.pop()     # stack에 요소중 마지막꺼 빼서 버림
            else:               # stack이 빈 리스트인데 닫힌괄호가 들어오면 (닫힌괄호가 열린괄호보다 더 많은 경우, 처음에 닫힌괄호가 들어오는경우)
                return "NO"     # 틀린문법
                
    if stack == []:             # append, pop 과정 끝낸 stack이 비어있으면
        return "YES"            # 갯수가 딱 맞았다는거니깐 맞는 문법
    else:                       # stack이 비어있지 않다면 (열린괄호가 닫힌괄호보다 더 많은 경우)
        return "NO"             # 틀린문법

print(is_bracket("[[[[]]]][]"))                     # YES
print(is_bracket("[[[[[[[[[[[[[[[[]]"))             # NO

 

성공! 재밌다

백스페이스랑 괄호 잘못치면 밑줄 그어지는거 진짜 이런 원리로 동작하는건가?

 

 

---