백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-9012 괄호 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/9012

반응형

솔루션 살펴보기!!

N = int(input())
results = []

for _ in range(N):
    testcase = input()
    cnt = 0
    is_valid = True

    for c in testcase:
        if c == '(':
            cnt += 1
        else:
            cnt -= 1

        if cnt < 0:
            is_valid = False
            break

    if is_valid and cnt == 0:
        results.append("YES")
    else:
        results.append("NO")

print("\n".join(results))

이 코드는 주어진 괄호 문자열이 올바르게 닫히는지 확인하는 문제를 해결하는 프로그램입니다. 이 문제는 괄호의 쌍이 맞는지 검사하는 문제로, 주로 스택(Stack)이나 카운터(Counter) 기법을 사용하여 해결할 수 있습니다.

코드 설명

입력 받기

N = int(input())

 

첫 번째 줄에서 입력되는 숫자 N은 테스트 케이스의 수를 나타냅니다.

결과 저장을 위한 리스트 초기화

results = []

results 리스트는 각 테스트 케이스의 결과를 저장하는 역할을 합니다.

테스트 케이스 처리

for _ in range(N):
    testcase = input()
    cnt = 0
    is_valid = True

N번 반복하면서 각 테스트 케이스를 입력받습니다. cnt는 현재 괄호의 균형 상태를 추적하며, is_valid는 해당 문자열이 유효한지 여부를 추적하는 변수입니다.

괄호 문자열 검증

for c in testcase:
    if c == '(':
        cnt += 1
    else:
        cnt -= 1

    if cnt < 0:
        is_valid = False
        break

문자열의 각 문자를 순회하면서:

• '('가 나오면 cnt를 1 증가시킵니다.
• ')'가 나오면 cnt를 1 감소시킵니다.
• cnt가 0보다 작아지면()가 (보다 많이 나온 경우) 즉시 is_valid를 False로 설정하고 반복을 중단합니다.

결과 저장

if is_valid and cnt == 0:
    results.append("YES")
else:
    results.append("NO")

반복이 끝난 후 cnt가 0이고, is_valid가 True인 경우(모든 괄호가 올바르게 짝을 이루는 경우) YES를, 그렇지 않은 경우 NO를 results 리스트에 저장합니다.

결과 출력

print("\n".join(results))

모든 테스트 케이스에 대한 결과를 출력합니다. results 리스트의 요소를 줄바꿈(\n)으로 구분하여 출력합니다.

728x90

알아야 할 주요 사전 지식

1. 스택(Stack) 개념: 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다. 괄호 문제에서는 스택을 사용하여 짝을 이루는 괄호를 검증하는 방식으로 주로 사용됩니다. 이 문제에서는 스택 대신 카운터(cnt)를 사용하여 균형을 검증합니다.
2. 문자열 순회(String Traversal): 문자열의 각 문자에 대해 순차적으로 접근하여 처리하는 방법입니다. 이 코드에서는 for 반복문을 사용하여 문자열의 각 문자를 하나씩 검사합니다.
3. 조건문(Conditional Statements): 코드에서 if, else 구문을 사용하여 특정 조건이 참일 때와 거짓일 때 다른 동작을 수행하도록 합니다. 여기서는 괄호의 균형이 맞는지 여부를 확인할 때 사용됩니다.

이 코드의 주요 목표는 괄호의 열림과 닫힘이 올바르게 이루어졌는지를 빠르고 효율적으로 검사하는 것입니다. 이를 위해 기본적인 문자열 처리와 조건 검사를 적절히 활용하고 있습니다.