SWE(4866)_괄호검사

작성일 | In

SWE 4866 괄호검사

아이디어

스택을 이용하여 괄호를 검사한다.

  1. 문자열 for문 돌면서 괄호 검사
  2. 왼쪽 괄호를 만나면 스택에 삽입
  3. 오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 뒤, 오른쪽 괄호와 짝이 맞는지 확인
    1. 스택이 비어있다 -> break
    2. 괄호의 짝이 안맞는다 -> break
    3. 문자열 끝까지 조사한 이후에도 스택에 괄호가 남아있다 -> break

배운 것

  1. python은 NULL 객체를 None으로 표현한다
  2. 또한 객체가 None인지 확인할 때는 is를 쓰는 걸 권장한다
  3. {(())}}에서 }가 남았을 때 예외처리 안해줘서 시간이 걸렸다.

코드


s = []


def push(item):
    s.append(item)


def pop():
    if len(s) == 0:
        # underflow
        return
    else:
        return s.pop(-1)


if __name__ == "__main__":
    T = int(input())
    for tc in range(1, T + 1):
        s = []  # s 초기화
        result = 1
        temp = input()
        for j in range(len(temp)):
            if(temp[j] == '(' or temp[j] == '{'):  # 여는 괄호면 push
                push(temp[j])
            elif(temp[j] == ')'):
                if(len(s) == 0):  # 비어있으면 break
                    result = 0
                    break
                else:
                    check = pop()
                    if(check != '('):  # 괄호 짝 맞는지 검사
                        result = 0
                        break
            elif(temp[j] == '}'):
                if(len(s) == 0):
                    result = 0
                    break
                else:
                    check = pop()
                    if(check != '{' or check is []):  # 괄호 짝 맞는지 검사
                        result = 0
                        break
        if(len(s) != 0):
            result = 0
        print("#%s %d" % (tc, result))

어거지로 완료해서.. 코드가 매우 지저분하다.

데브로그님의 코드 참조

TC = int(input())

for tc in range(1, TC+1):
    Data = input()
    N = len(Data)
    stack = []
    for i in range(N):
        #여는 괄호가 올 경우 => stack에 저장
        if Data[i] == "(" or Data[i] == "{":
            stack.append(Data[i])
        elif Data[i] == ")" or Data[i] == "}":
            #닫는 괄호 이며 stack이 빈 경우 => 처음부터 닫는 괄호가 오는 경우
            if len(stack) == 0:
                stack = [Data[i]]
                break
            #stack에 저장된 괄호와 일치하지 않는 경우
            elif (Data[i] == "}" and stack[-1] !="{") or (Data[i] == ")" and stack[-1] != "("):
                stack = [Data[i]]
                break
            #stack에 저장된 괄호와 일치하는 닫는 괄호가 오는 경우
            else:
                stack.pop()

    if not len(stack):
        print(f'#{tc} 1')
    else:
        print(f'#{tc} 0')

시간을 잡아 먹는 점

왜 안풀리는 거냐고 씩씩대며.. 계속 몫을 구하는 연산자를 사용하고 있었다. 시간이 간다고 조급해 하지말자 ..

참고자료

0%