[BOJ] 4949번 - 균형잡힌 세상 (Swift, C++)

문제

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

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

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

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

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

 

<문제 링크>

4949번: 균형잡힌 세상

---

입력

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

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

---

출력

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

---

문제 풀이

괄호의 짝이 맞게 이루어져 있는지 확인하는 문제입니다.

예를 들어, 아래와 같은 상황이 옳은 예시라고 할 수 있습니다.
( ) ( ) [ ] 

[ ( ) ( ) ]

[ ( ( ) ) ]

 

그렇다면 잘못된 상황은 무엇이 있을까요?

 

닫힌 괄호가 열린 괄호보다 먼저 나오는 경우와

열린 괄호 다음으로 오는 닫힌 괄호가 짝이 맞지 않는 경우가 있습니다.

 

문자열을 순회하며 닫힌 괄호가 나온다면 저장을 해뒀다가 닫힌 괄호가 나오는 순간 

조건문을 활용하여 상황을 판단하면 처리를 해주면 될 것 같습니다.

 

괄호를 저장할 자료구조로는 많은 것들이 있지만 닫힌 괄호를 판단할 때 중요한 것은

최근에 저장된 닫힌 괄호이므로 FILO방식의 스택을 이용하여 괄호를 저장하겠습니다.

 

풀이 순서

1. 열린 괄호가 나온다면 스택에 저장합니다.

2. 닫힌 괄호가 나온다면 문제 조건에 따라 처리를 해줍니다.

- 만약, 닫힌 괄호가 짝이 없이 먼저 나온다면 "no"

- 이전 열린 괄호가 닫힌 괄호와 짝이 맞지 않는다면 "no"

- 이전 열린 괄호와 닫힌 괄호와 짝이 맞다면, 닫힌 괄호를 스택에서 제거합니다.

3. 스택의 상태를 확인하여 결과를 출력해줍니다.

 

❗️추가 반례 (질문 게시판 활용)

아래는 다 "no"를 출력해야 합니다.

• ([(]])
• ([)]).
  .
• (()))
  .
  
• [(()]).
  .
• (
• (
  .
  

---

풀이 코드

< Swift>

// Swift
// 첫 번째 코드
while let str = readLine(), str != "." {
    
    var s = [Character]()  // stack
    
    for char in str {
        
        if char == "[" || char == "(" {
            s.append(char)
        } else if let last = s.last {
            if (last == "[" && char == ")") || (last == "(" && char == "]") { // 닫는 괄호와 스택의 top 괄호가 짝이 아니라면
                break
            } else if last == "[" && char == "]" {  // 짝이 맞다면
                s.removeLast()
            } else if  last == "(" && char == ")" {
                s.removeLast()
            }
        } else if char == "]" || char == ")" {  // 닫는 괄호가 먼저 나오면
            s.append(char)  //  스택에 push하고 반복문 종료
            break
        }
    }
    
    // 스택에 괄호 유무 확인
    if !s.isEmpty {
        print("no")
    } else {
        print("yes")
    }
}

// Swift
// 최적화
while let str = readLine(), str != "."  {
    
    var s = [Character]()  // stack
    var isValid = true
    
    for a in str {
        if a == "(" || a == "[" {
            s.append(a)
        } else if a == ")" {
            if s.isEmpty || s.last != "(" {
                isValid = false
                break
            } else {
                s.removeLast()
            }
                
        } else if a == "]" {
            if s.isEmpty || s.last != "[" {
                isValid = false
                break
            } else {
                s.removeLast()
            }
        }
    }
    
    if s.isEmpty && isValid {
        print("yes")
    } else {
        print("no")
    }
    
}

---

< C++>

// C++
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    while(true){
        string a;
        getline(cin, a);
        if(a == ".") break;
        
        stack<char> s;
        bool isValid = true;
        
        for (auto c : a){
            if(c == '(' || c == '[') s.push(c);
            else if(c == ')'){
                if(s.empty() || s.top() != '('){ 
                    isValid = false;
                    break;
                }
                
                s.pop();
            }
            else if(c == ']'){
                if(s.empty() || s.top() != '['){
                    isValid = false;
                    break;
                }
                s.pop();
            }
            
        }
        
        if(isValid && s.empty()){
            cout << "yes" << '\n';
        } else cout << "no\n";
    }
}

---

마무리

모든 예외 상황을 고려하여 코드를 작성해야 한다는 점은 매우 중요합니다.저는 처음에 다른 짝의 괄호가 오는 예외를 코드에 작성하지 않아 오랜 시간 고민을 했습니다. 😭

 

또한, 모든 예외를 고려했다고 해도, 해당 논리를 코드에 잘 녹여내는 것도 중요합니다.예를 들어, Swift의 경우 두 개의 코드를 작성했는데,  같은 논리의 코드라도 쉽게 이해할 수 있는 코드가 더 좋은 코드입니다.

 

모든 예외 상황을 고려하고, 해당 논리를 코드에 쉽게 구현하는 연습도 해야할 것 같습니다. 🤓