[SWEA] 1218 - 괄호 짝짓기

문제

4 종류의 괄호문자들 '()', '[]', '{}', '<>' 로 이루어진 문자열이 주어진다.

이 문자열에 사용된 괄호들의 짝이 모두 맞는지 판별하는 프로그램을 작성한다.

예를 들어 아래와 같은 문자열은 유효하다고 판단할 수 있다.

아래와 같은 문자열은 유효하지 않은 문자열이다. 붉은색으로 표시된 괄호의 짝을 찾을 수 없기 때문이다.

아래 문자열은 열고 닫는 괄호의 개수는 유효하나 짝이 맞지 않는 괄호가 사용 되었기 때문에 유효하지 않다.

[입력]

각 테스트 케이스의 첫 번째 줄에는 테스트케이스의 길이가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 유효성 여부를 1 또는 0으로 표시한다 (1 - 유효함, 0 - 유효하지 않음).

풀이

입력받은 string을 0번부터 끝까지 순회하면서,
여는 괄호가 나오면 str_stack에 모두 push하고, 닫는 괄호가 나오면 str_stack의 제일 마지막 괄호와 짝이 맞으면 pop시킨다. 중간에 짝이 맞지않으면 반복문을 종료하고 result=0을 출력한다. 반복문이 정상적으로 종료되면 str_stack의 길이를 재서 0이면 짝이 다 맞은것이므로 resul=1을 출력한다.

코드1

a = ['(','[','{','<']
b = [')',']','}','>']
for test_case in range(1, 11):
    length = int(input())
    string = input()
    str_stack=[]

    for i in range(len(string)):
        if string[i] in a:
            str_stack.append(string[i])
        elif string[i] in b:
            if string[i] == b[0] and str_stack[-1] == a[0]:
                str_stack.pop()
            elif string[i] == b[1] and str_stack[-1] == a[1]:
                str_stack.pop()
            elif string[i] == b[2] and str_stack[-1] == a[2]:
                str_stack.pop()
            elif string[i] == b[3] and str_stack[-1] == a[3]:
                str_stack.pop()
            else:
                result=0
                break
    if len(str_stack) == 0:
        result=1

    print(f'#{test_case} {result}')

코드2

a = ['(','[','{','<']
b = [')',']','}','>']
for test_case in range(1, 11):
    length = int(input())
    string = input()
    str_stack=[]

    for i in range(len(string)):
        if string[i] in a:
            str_stack.append(string[i])
        elif string[i] in b:
            if a.index(str_stack[-1]) == b.index(string[i]):
                str_stack.pop()
            else:
                result=0
                break
    if len(str_stack) == 0:
        result=1

    print(f'#{test_case} {result}')