[코딩테스트] 스택(Stack) 활용 - 수식의 괄호 쌍

 

수식의 괄호 쌍

• 주어진 괄호 문자열이 올바른지 판단하는 문제
• 여는 괄호는 스택에 넣고, 닫는 괄호는 스택에 있는 여는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애면 된다. 
• 짝을 짓지 않는 여는 괄호가 남아있거나, 짝을 짓지 못한 닫는 괄호가 남아있으면 오답이다. 

 

구현 

스택으로 구현 가능하다.

1. 여는 괄호가 나오면 스택에 추가
2. 닫는 괄호가 나오면 
   1. 스택이 비어있으면 -> 올바르지 않는 괄호 쌍
   2. 스택의 top이 짝이 맞지 않는 괄호이면 -> 올바르지 않는 괄호 쌍
   3. 스택의 top이 짝이 맞는 괄호이면 -> pop
3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 -> 올바르지 않은 괄호 쌍
4. 모든 과정을 끝낸 후 스택에 괄호가 남아있지 않으면 -> 올바른 괄호 쌍

 

 

 

코드 - BOJ 4949

internal class BOJ4949_균형잡힌_세상
{
    static void Main(string[] args)
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());
        StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        Stack<char> stack = new Stack<char>();

        string input = sr.ReadLine();
        while(input != ".")
        {
            if (IsBalanced(stack, input))
                sw.WriteLine("yes");
            else
                sw.WriteLine("no");

            stack.Clear();
            input = sr.ReadLine();
        }

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

    public static bool IsBalanced(Stack<char> stack, string input)
    {
        foreach(char c in input)
        {
            if (c == '(')
                stack.Push(c);
            else if (c == '[')
                stack.Push(c);
            else if(c == ')')
            {
                if (stack.Count == 0)
                    return false;
                else if (stack.Peek() != '(')
                    return false;
                else if (stack.Peek() == '(')
                    stack.Pop();
            }
            else if(c == ']')
            {
                if (stack.Count == 0)
                    return false;
                else if (stack.Peek() != '[')
                    return false;
                else if (stack.Peek() == '[')
                    stack.Pop();
            }
        }

        if (stack.Count != 0)
            return false;
        else
            return true;
    }
}

 

 

복습1 풀이 (5/18)

수식의 괄호 쌍 문제다. 

문제를 풀기 전 배웠던 내용을 다시 되짚어보자. 

 

수식의 괄호쌍. 주어지 괄호 문자열이 올바른지 판단하는 문제다. 

괄호 문자열을 제외한 문자열이 뭐든 상관없다. 그냥 괄호 문자열만 일치하는지 확인하면 된다. 

 

그러면 일치하는 괄호쌍과 일치하지 않는 괄호쌍을 어떻게 찾는지 정리해보자. 

 

일단 여는 괄호 문자열( '(', '[' )은 Stack에 넣자. 

닫는 괄호 문자열 ( ')', ']' )이 나오면 Stack의 Peek와 비교해서 일치하는 괄호쌍인지 확인하자. 

1. Stack의 Peek와 닫는 괄호 문자열이 일치하면 -> Stack의 Peek를 Pop하자. 

2. Stack의 Peek와 닫는 괄호 문자열이 일치하지 않으면 -> "no"를 출력한다. 

3. 닫는 괄호 문자열과 비교할 여는 괄호가 Stack에 없으면 -> "no"를 출력한다. 

4. 1,2,3 과정을 다 확인하고 Stack에 남아있는 괄호가 있으면, 여는 괄호가 아직 남아있으므로 -> "no"를 출력한다. 

5. 1,2,3 과정을 다 확인하고 Stack에 남아있는 괄호가 없으면, 모든 괄호가 일치하므로 "yes"를 출력한다. 

6. 일치 여부를 출력했으면 Stack을 비우자. 

7. 위 과정을 "."가 입력될 때까지 반복하자.

 

 

복습1 코드 - 정답

using System.Text;

public class BOJ4949
{
    static StreamReader sr = new StreamReader(Console.OpenStandardInput());
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
    static StringBuilder sb = new StringBuilder();

    static Stack<char> stack = new Stack<char>();

    public bool IsBalanced(string input1)
    {
        foreach(char c in input1)
        {
            if(c == '(')
            {
                stack.Push(c);
            }
            else if(c == '[')
            {
                stack.Push(c);
            }
            else if(c == ')')
            {
                if(stack.Count == 0)
                {
                    return false;
                }
                if(stack.Peek() == '(')
                {
                    stack.Pop();
                }
                else
                {
                    return false;
                }
            }
            else if(c == ']')
            {
                if(stack.Count == 0)
                {
                    return false;
                }
                if(stack.Peek() == '[')
                {
                    stack.Pop();
                }
                else
                {
                    return false;
                }
            }
        }

        // 남이있는 괄호가 있다면 
        if(stack.Count > 0)
        {
            return false;
        }
        
        return true;
    }

    static void Main(string[] args)
    {
        BOJ4949 b = new BOJ4949();

        string input1 = "";

        // 입력 문자열이 "." 일때까지 반복
        while (true)
        {
            input1 = sr.ReadLine();
            if(input1.Equals("."))
            {
                sb.AppendLine("yes");
                break;
            }

            if (b.IsBalanced(input1))
            {
                sb.AppendLine("yes");
            }
            else
            {
                sb.AppendLine("no");
            }

            // 
            stack.Clear();
        }

        sw.WriteLine(sb.ToString());

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