[백준 BOJ] 4949번(균형잡힌 세상) Python 풀이

# 해당 포스팅은 이제 막 알고리즘 공부를 시작한 초보 수준(백준 실버 등급)에서 작성했음을 이해해주시고, 비난보다는 따뜻한 조언을 부탁드립니다.

---

안녕하십니까, 간토끼입니다.

알고리즘 첫 포스팅인데요. 급하게 코딩테스트를 처음 준비하면서 알고리즘 공부란 걸 처음으로 해봤습니다.

백준 문제를 푼지 4일차입니다. ㅜㅜ

 

첫 포스팅은 백준 4949번 (균형잡인 세상)에 대해 다뤄보겠습니다.

 

1. 문제 링크

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞는지 판단하는 프로그램을 짜는 것입니다.

문자열에 포함되는 괄호는 소괄호 ( ), 대괄호 [ ] 두 종류이고, 균형을 이루는 조건은 다음과 같습니다.

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

 

입력으로는 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호, 대괄호로 이루어져있고, 온점(".")으로 끝나는 문자열이 주어지고, 입력의 종료 조건은 공백없이 "." 하나만 입력되는 경우입니다. 

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

 

2. 접근 방법

다음과 같이 접근하였습니다.

먼저 스택 구조를 활용했습니다.

파이썬에서는 기본적으로 list를 이용해서 스택을 구현할 수 있으므로 별도의 라이브러리를 이용할 필요가 없습니다.

문자열의 i번째 값이 왼쪽 괄호인 ( or [ 라면 list에 추가(append)했으며,

문자열의 j번째 값이 오른쪽 괄호 ) or ] 라면 왼쪽 괄호 리스트(left_list)에서 pop을 통해 마지막으로 추가된 괄호를 꺼냈으며,

이때 꺼낸 괄호와 j번째 값(오른쪽 괄호)가 균형이 맞는지를 판단했습니다.

 

놓칠 만한 부분이 종료 조건이라고 생각하는데요.

공백 없이 "." 만 주어지는 경우 종료하는 조건은 주어진 문자열의 0번째 index의 값이 "."인지 여부를 판단하게 해서 맞다면 종료시키게 했습니다.

또한 대표적인 반례 중 ( (  ) . 처럼 아직 처리되지 않은 왼쪽 괄호가 남아있는 상태에서 "."을 만났을 때 종료하고 "yes"를 반환하는 경우가 있는데요.

이땐 주어진 i번째 문자열의 끝인 "."이 주어졌을 때, 만약 left_list에 남은 값이 있다면 "no"를 반환하게 하면 됩니다.

 

3. 코드

# 백준 : 4949 균형잡힌 세상
# 풀이방법 : Stack 활용

result = [] # 결과값 list (yes or no)

# 중첩 while문 구현
while True:
    sentence = input() # 입력받을 문자열
    left_list = [] # 왼쪽 괄호만 모아놓을 list
    error = 0
    i = 0
    if sentence[0] == ".": # 프로그램 종료 조건
        break
    
    while True:
        a = sentence[i]
        if a == ".": # 개별 문자열의 종료 조건
            if len(left_list) > 0:
                error += 1
            break
            
        if a == "[" or a == "(":
            left_list.append(a)
        
        elif a == "]":
            try:
                b = left_list.pop()
            except:
                error += 1
                break
            
            if b == "[":
                pass
            else:
                error += 1
                
        elif a == ")":
            try:
                b = left_list.pop()
            except:
                error += 1
                break
                
            if b == "(":
                pass
            else:
                error += 1
        i += 1
    
    if error == 0:
        result.append("yes")
    else:
        result.append("no")
        
        
print(*result, sep = '\n')

 

감사합니다.

잘 읽으셨다면 게시글 하단에 ♡(좋아요) 눌러주시면 감사하겠습니다 :)

(구독이면 더욱 좋습니다 ^_^)

* 본 블로그는 학부생이 운영하는 블로그입니다.

따라서 포스팅에 학문적 오류가 있을 수 있으며, 이를 감안해서 봐주시면 감사하겠습니다.

 

---

- 간토끼(DataLabbit)

- B.A. in Economics, Data Science at University of Seoul