[백준/C#] 4949 - 균형잡힌 세상

1. 문제

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

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

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

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

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

 

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

 

- 입력

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

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

 

- 출력

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

 

- 설명

9012-괄호 문제와 같은데 괄호의 종류가 다양해진 문제

예제 입력	예제 출력
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)]. ([ (([( [ ] ) ( ) (( ))] )) ]).  . .	yes yes no no no yes yes

4949번: 균형잡힌 세상

---

2. 풀이

여기서도 9012번 문제 풀이와 같이 괄호를 스택에 저장한 후 올바른 괄호 쌍이 이루어지면 스택에서 빼내는 방법을 썼다.

차이점은 괄호가 두 종류라서 괄호가 짝이 맞는지 검사하는 부분이 추가됐다.

짝이 이루어지지 않으면 스택에 남기고, 반복문이 끝나고 괄호 스택이 비어있지 않으면 균형 잡힌 문자열이 아닌 것이다.

 

문자열에 알파벳도 섞여있어서, 아스키코드를 이용해 스택에 괄호만 저장하도록 걸러냈다.

괄호들의 아스키코드값은 40, 41, 91, 93이다.

// 균형잡힌 세상
// 65-90, 97-122
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

while (true) {
    string input = sr.ReadLine();
    Stack<char> stack = new Stack<char>();

    // 입력이 점 하나면 입력이 끝났다는 뜻
    if (input == ".") break;

    for (int j = 0; j < input.Length; j++) {
        if (input[j] != 40 && input[j] != 41 && input[j] != 91 && input[j] != 93)
            continue;
        else {
            if (input[j] == '(' || input[j] == '[') stack.Push(input[j]);
            else {
                if (stack.Count == 0) stack.Push(input[j]);
                else {
                    if (stack.Peek() == '(' && input[j] == ')') stack.Pop();
                    else if (stack.Peek() == '[' && input[j] == ']') stack.Pop();
                    else stack.Push(input[j]);
                }
            }
        }

    }

    if (stack.Count == 0) sw.WriteLine("yes");
    else sw.WriteLine("no");                
}

sr.Close();
sw.Close();

 

---