프로그래밍_백준/Python

Python) 9012번 괄호 문제 (stack)

공부하려구요 2023. 8. 7. 16:09
728x90
반응형

괄호가 올바르게 균형을 이루었는지 확인하는 문제입니다. 스택을 사용한 방법, 사용하지 않은 방법 두 가지로 문제를 풀었습니다.

 

첫 번째

  1. 문자열의 개수를 입력받습니다.
  2. 각 문자열에 대해 입력을 받아 bracket_list에 저장합니다.
  3. 문자열 길이의 홀수 여부를 확인하여 짝수문자열인 경우에만 올바른 조합 검증을 수행합니다.
  4. 문자열 내부에서 여는 괄호와 닫는 괄호의 개수를 세어 올바른 조합 여부를 판정합니다
a = int(input())  # 테스트 케이스의 수를 입력받습니다.
bracket_list = []  # 괄호 문자열을 저장할 리스트를 초기화합니다.
count_open = 0  # 여는 괄호의 개수를 추적하기 위한 변수를 초기화합니다.
count_close = 0  # 닫는 괄호의 개수를 추적하기 위한 변수를 초기화합니다.

for i in range(a):
    bracket = list(input())  # 한 줄의 괄호 문자열을 입력받고 리스트 형태로 변환합니다.
    bracket_list.append(bracket)  # 입력받은 괄호 문자열을 리스트에 추가합니다.

for i in range(a):  # 테스트 케이스 수만큼 반복하여 각 문자열을 검사합니다.
    if len(bracket_list[i]) % 2 != 0:  # 문자열 길이가 홀수이면 올바른 괄호 문자열이 아닙니다.
        print("NO")
        continue
    else:
        for j in range(int(len(bracket_list[i]))):  # 문자열 내의 괄호들을 검사합니다.
            if count_open < count_close:  # 여는 괄호보다 닫는 괄호 수가 더 많으면 올바르지 않습니다.
                break
            if bracket_list[i][j] == "(":  # 여는 괄호를 발견하면 개수를 증가시킵니다.
                count_open += 1
            else:  # 닫는 괄호를 발견하면 개수를 증가시킵니다.
                count_close += 1

        if count_open == count_close:  # 여는 괄호와 닫는 괄호의 개수가 같으면 올바른 괄호 문자열입니다.
            print("YES")
        else:  # 괄호의 개수가 일치하지 않으면 올바르지 않습니다.
            print("NO")

        count_open = 0  # 다음 문자열 검사를 위해 여는 괄호 개수를 초기화합니다.
        count_close = 0  # 다음 문자열 검사를 위해 닫는 괄호 개수를 초기화합니다.

두 번째 방식은 스택을 사용한 방법입니다.

1. 테스트 케이스 수를 입력받습니다.
2. 각 테스트 케이스에 대해:

  • 스택을 초기화합니다.
  • 입력받은 문자열의 각 문자를 탐색합니다.
  • 여는 괄호('(') 를 발견하면 스택에 추가합니다.
  • 닫는 괄호(')') 를 발견하면,
    • i. 스택이 비어있지 않다면, 스택에서 마지막 괄호를 꺼냅니다.
    • ii. 스택이 비어있다면, 올바르지 않은 조합이므로, 출력하고 반복문을 종료합니다.
  • 반복문이 끝날 때 (break로 종료되지 않았을 때), 스택이 비어있으면 올바른 조합이므로 'YES'를 출력합니다. 그렇지 않으면 'NO'를 출력합니다.
T = int(input())

for i in range(T):
    stack = []  # 괄호들을 저장할 스택을 초기화합니다.
    brackets = input()
    for bracket in brackets:
        if bracket == '(':
            stack.append(bracket)
        elif bracket == ')':
            if stack:  # 스택이 비어있지 않으면, 최근 여는 괄호를 제거합니다.
                stack.pop()
            else:  # 스택이 비어있으면, 괄호가 제대로 닫히지 않았기 때문에 "NO"를 출력하고 반복문을 종료합니다.
                print("NO")
                break
    else:  # break 문으로 끊기지 않고 완료되면 괄호 검사를 수행합니다.
        if not stack:  # 스택이 비어있으면 괄호가 모두 올바르게 닫힌 것입니다.
            print("YES")
        else:  # 스택에 남아 있는 괄호가 있다면 "NO"를 출력합니다.
            print("NO")
728x90
반응형