코딩테스트 19일차(2025.02.06) - 백준4949번(균형잡힌 세상)

문제유형

스택

풀이 방법 도출 과정

1. "("는 ")"와 짝꿍 "["는 "]"과 짝궁 이를 맞추지 않고 있다면, no출력 그 반대는 yes출력을 한다. "."는 줄이 끝났다는 신호이다.

2. 스택을 활용하면 괄호의 올바른 짝을 쉽게 확인할 수 있음

3. 왼쪽 괄호를 만나면 스택에 추가

4. 오른쪽 괄호를 만나면 스택에서 짝이 맞는 괄호가 있는지 확인 후 제거.

- 짝이 맞지 않으면 no 출력

- 짝이 맞지 않거나 스택이 비어있는데 닫는 괄호가 나오면 no 출력

5. 모든 문자열을 처리한 후에도 스택에 괄호가 남아 있으면 no 출력

- 스택이 비어 있으면 yes 출

 

시간 복잡도

시간복잡도는 for문이 입력되는 순서대로 적용되고 있기에 대략 O(n)로 보여진다. 그리고 for 문의 스택의 연산은 O(1)이다. 그렇기 때문에 다 합쳐서 시간 복잡도는 O(n)이다.

코드 및 간단설명

스택을 구현하고 이를 활용하여 값이 맞는지 안맞는지 확인하는 코드이다.

stack = []

while True:
    try:
        A = input()
        if A == ".":  # 입력이 '.'이면 종료
            break

        stack = []  # 새로운 문자열을 검사할 때마다 스택 초기화
        is_balanced = True  # 괄호 균형 여부

        for i in A:
            if i == "[" or i == "(":
                stack.append(i)
            elif i == "]":
                if not stack or stack[-1] != "[":
                    is_balanced = False
                    break
                stack.pop()
            elif i == ")":
                if not stack or stack[-1] != "(":
                    is_balanced = False
                    break
                stack.pop()

        if is_balanced and not stack:
            print("yes")
        else:
            print("no")

    except EOFError:
        break