백준#2529 - 부등호

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

2529번: 부등호

그리디 알고리즘으로 분류된 2529 부등호 문제 입니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _2529
{
    class Program
    {
        static void Main(string[] args)
        {
            int kCount = int.Parse(Console.ReadLine());
 
            //부등호를 입력 받아 공백 제거.
            string input = Console.ReadLine().Replace(" ", "");
 
            var numStack = new Stack<int>();
            numStack.Push(9);
            int startNum = 9;
 
            {
                //최댓값 구하는 과정.
                for (int i = 0; i < input.Length; i++)
                {
                    //부등호 > 를 만나면 스택의 모든 값 출력.
                    if (input[i] == '>')
                    {
                        while (numStack.Count > 0)
                            Console.Write(numStack.Pop());
                    }
                    numStack.Push(--startNum);
 
                }
 
                //남은 스택의 값 모두 출력.
                while (numStack.Count > 0)
                    Console.Write(numStack.Pop());
                Console.WriteLine("");
            }
 
            startNum = 0; ;
            numStack.Clear();
            numStack.Push(0);
            //최솟값 구하는 과정.
            {
                for (int i = 0; i < input.Length; i++)
                {
                    //부등호  < 를 만나면 스택의 모든 값 출력.
                    if (input[i] == '<')
                    {
                        while (numStack.Count > 0)
                            Console.Write(numStack.Pop());
                    }
                    numStack.Push(++startNum);
                }
 
                while (numStack.Count > 0)
                    Console.Write(numStack.Pop());
            }
 
        }
    }
}
 

 

최댓값 구하는 방법.

우선 최댓값을 만들고 싶다면 9 8 7 6 이런 식으로 큰 것부터 줄을 세우고 싶습니다. 하지만 부등호가

< < < < 이런 식으로 수가 증가하는 방향으로 나온다면 오름차순으로 나올 것입니다. 4개의 < 부등호가

있다면 5 < 6 < 7 < 8 < 9 이런식으로 줄을 세워야만 합니다.

 

줄을 세워야 한다는 것이 중요합니다. 언제까지 줄을 세울 수 있냐면 다음 > 을 만나거나 끝날 때 까지 입니다.

저는 이걸 줄세우기 위해 스택을 사용했습니다.

 

먼저 startNum을 9로 세팅하고 Stack에 넣었습니다. 그리고 다음 부등호를 보는데 < 라면 9보다 큰

수가 올 수 없기에 8을 스택에 넣고 다음 반복을 진행 합니다.

 

다음 부등호가 > 라면 스택에 있는 것들을 출력합니다 Top에 8, 다음 9가 있으므로 8과 9를 출력합니다.

다음 7을 스택에 넣어줍니다. 이렇게 반복하면 < 부등호가 나오는 동안 차례로 줄을 세우며 > 부등호가

나오면 스택의 모든 것을 출력 하고 startNum을 하나 줄여 스택에 넣어줍니다.

 

마지막으로 끝에 도달하면 Stack에 남아있는 모든 것을 출력합니다.

 

최솟값 구하는 방법.

최댓값이 <를 만나는 동안 5, 6, 7, 8, 9 이런 식으로 줄을 세웠다면 최솟값은 반대로

> 를 만나는 동안 4, 3, 2, 1, 0 이런 식으로 줄을 세워야 합니다. 이 또한 마찬가지 입니다.

 

처음 startNum을 0 으로 stack에 0을 넣어줍니다. >를 만나면 Stack에 startNum++를 넣고 반복하며

< 부등호를 만나면 3, 2, 1, 0이런 식으로 줄을 선 다음 다시 줄을 서야 하므로 Stack의 모든 것을

출력하고 startNum++ 를 Stack에 넣어줍니다. 마지막으로 Stack의 모든것을 출력해줍니다.

 

최댓값 구하는 것과 조건만 다를 뿐 완전히 동일합니다.