[스택] 코딩테스트 문제 TIL (균형잡힌 세상) - 백준 4949번

말하는 감자·2024년 12월 11일

baekjoon data structure python stack 백준 스택 자료 구조 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

31/67

이번주부터 본격적으로 스택, 큐 자료구조의 유형을 다시 풀기 시작했습니다. 저번주까지 진행했던 연결 리스트 유형의 문제들은 주로 LeetCode에서 풀었고 푼 문제들은 다음 링크에서 확인할 수 있습니다.

그럼 오늘 문제를 확인해볼까요?

1. 오늘의 학습 키워드

스택
LIFO

2. 문제: 백준 4949번. 균형잡힌 세상

단계: 🥈실버 4단계
주제: 자료 구조, 문자열, 스택
출처: https://www.acmicpc.net/problem/4949

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입력 1 복사

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

예제 출력 1 복사

yes
yes
no
no
no
yes
yes

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

3. 문제 풀이

Step1. 문제 이해하기

흔히 하는 유효한 괄호 찾기 문제입니다. 다만 괄호만 존재하지 않고 영문 알파벳, 공백, 온점이 있습니다.

괄호는 소괄호("()") 와 대괄호("[]")로 2종류입니다. 그리고 입력의 종료조건으로 맨 마지막에 온점 하나가 들어옵니다. 하지만 이것은 온점 하나가오는 것이지 다른 것과 함께 온다면 종료조건이 아닙니다!

입출력을 살펴보도록 하겠습니다.

Input:
- 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같습니다.
- 시간 복잡도 상으로는 정말 여유로워 보입니다.
Output:
- 각 줄마다 해당 문자열이 균형을 이루고 있으면 “yes”를, 아니면 “no”를 출력합니다.

문제 이해는 어느정도 완료가 되었습니다. 이제 구현을 위해 어떻게 접근을 해야 할지 고민해보겠습니다.

Step2. 문제 분석하기

주어진 문제는 문자열이 균형을 이뤄야 합니다.

모든 열린 소괄호는 닫히는 소괄호와 대칭을 이뤄야 합니다.

즉, 열린 소괄호와 다른 문자열이 들어오면 반응을 하지 않다가 닫힌 대괄호가 들어왔을 때, 대칭이 되는지 아닌지를 판단하는 반응이 일어나야 합니다.

따라서, LIFO원리를 사용하기 때문에 스택 자료구조를 사용해야 합니다.

그렇다면 열린 소괄호가 들어온다면 스택 자료구조에 값을 넣습니다. 그러다가 닫힌 소괄호(”)”, “]”)가 들어왔을 때 어떤 조건에 따라 처리를 하여 해당 문자열이 균형을 이루는지, 아닌지를 판단하면 해결이 됩니다!

위 내용을 기반으로 코드 설계 과정으로 넘어가도록 하겠습니다.

Step3. 코드 설계하기

입력 처리:
- 입력이 여러 줄로 들어오므로, sys.stdin.readline()을 사용하여 입력을 받습니다.
- 종료 조건은 입력 문자열이 '.'인 경우입니다. 이 경우 반복문을 종료합니다.
스택 사용:
- 균형을 판단하기 위해 스택 자료구조를 사용합니다.
- 열린 괄호 ( 또는 [는 스택에 추가합니다.
- 닫힌 괄호 ) 또는 ]는 스택의 맨 위에 있는 열린 괄호와 비교하여 유효성을 판단합니다.
  - 스택이 비어 있거나, 괄호가 서로 매칭되지 않으면 균형이 깨졌다고 판단(flag = False).
  - 매칭되면 스택에서 열린 괄호를 제거(stack.pop()).
문자열 순회:
- 입력 문자열을 한 글자씩 순회하며, 괄호만 처리합니다. 알파벳이나 공백 등 다른 문자들은 무시합니다.
결과 판단:
- 문자열 순회가 끝난 후:
  - 스택이 비어 있고(not stack), flag가 True라면 문자열은 균형잡힌 상태로 판단하고 "yes"를 출력합니다.
  - 그렇지 않으면 "no"를 출력합니다.

Step4. 코드 구현하기

import sys

while True:
    text = sys.stdin.readline().rstrip()
    if text == '.':
        break
    stack = []
    flag = True
    
    for t in text:
        if t == '(' or t == '[':
            stack.append(t)
        elif t == ')':
            if not stack or stack[-1] == '[':
                flag = False
                break
            stack.pop()
        elif t == ']':
            if not stack or stack[-1] =='(':
                flag = False
                break
            stack.pop()
        
    if not stack and flag:
        print('yes')
    else:
        print('no')

코드 설명:
- 스택 사용:
  - 열린 괄호는 스택에 추가하여 나중에 닫힌 괄호와 매칭 여부를 검사합니다.
  - 닫힌 괄호가 들어오면 스택의 맨 위 요소와 비교합니다.
    - 매칭되는 경우 스택에서 해당 열린 괄호를 제거합니다.
    - 매칭되지 않거나 스택이 비어 있으면 균형이 깨졌다고 판단합니다.
- flag 변수:
  - 문자열 순회 중 균형이 깨지는 경우(flag = False) 즉시 순회를 종료합니다.
- 결과 판단:
  - 스택이 비어 있어야 모든 열린 괄호가 매칭되었다는 것을 의미합니다.
  - flag가 True일 때만 균형이 잡힌 것으로 간주합니다.
시간 복잡도:
- 문자열 순회:
  - 문자열 길이를 n이라 할 때, 각 문자열은 한 번씩 순회하므로 O(n).
- 스택 연산:
  - 각 문자에 대해 append 또는 pop을 수행하므로, 스택 연산은 O(1)입니다.
- 전체 시간 복잡도:
  - 입력 문자열의 총 길이를 N이라고 하면, 시간 복잡도는 O(N).
결과: