[코딩테스트] BOJ 17298 - 오큰수(실패)

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

17298번: 오큰수

 

 

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

 

 

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

 

예제 입력 1

4
3 5 2 7

 

예제 출력 1

5 7 7 -1

 

 

예제 입력 2

4
9 5 4 8

 

예제 출력 2

-1 8 8 -1

 

 

풀이

일단 이 문제는 O(N^2) 풀이가 안 된다. 

N은 최대 1,000,000이다. 1,000,000의 제곱은 1,000,000,000,000이다. 최악의 경우 1조 번의 연산을 한다. 

컴퓨터는 1초에 대략 3억~5억 번의 연산을 한다. N^2번 연산을 하면 1조 번의 연산을 하므로 시간 초과가 난다. 

따라서 O(N^2) 풀이로 풀어선 안 된다. 

 

O(N^2) 풀이는 간단하게 떠올릴 수 있다. 

그냥 이중 for문으로 푸는 것이다. i번째 수를 i+1, i+2, ... 와 비교해서 오큰수를 찾는 것. 

이 풀이를 피하면 된다. 

 

그러면 어떻게 풀 수 있을까. 

어떻게 하면 O(N) 혹은 이 보다 더 적은 연산을 하고 문제를 풀 수 있을까. 

 

일단 오큰수를 알려면 옆에 있는 숫자들을 알아야 한다. 

 

옆에 있는 숫자들을 미리 변수에 저장해둬야 할까?

숫자 하나씩 비교해 가면서 한 턴에 끝내야 할까? 

 

옆에 있는 숫자들을 미리 변수에 저장해 두려면 어떻게 해야 할까? 

그냥 숫자들을 스택에 다 넣어두면 될 것 같다. 

그러고 나서? 그 숫자들로 오큰수를 찾으면 될 것 같긴 한데, 어떻게 할지 잘 모르겠다. 

이중 for문 형태로 구현해야 하는 풀이만 떠오른다. 

 

숫자 하나씩 비교해 가면서 한 턴에 끝내려면 어떻게 해야 할까? 

어제 배웠던 생각의 전환을 적용해 보자. 

이 문제를 보면 일반적으로 이 숫자의 오큰수는 무엇일까 생각하고 옆에 있는 숫자를 보고 오큰수를 찾는다. 

그런데 이걸 그대로 구현하려니 잘 안된다. 

다르게 생각해 보자. "이 숫자는 오큰수일까?" 라고 생각해보는 건 어떨까? 

 

3 5 2 7이 입력되었다고 생각해보자. 

5는 3의 오큰수일까? 맞다. 5를 출력한다. 

2는 5의 오큰수일까? 아니다. 그러면 7은 5의 오큰수일까? 맞다. 7을 출력한다. 

7은 2의 오큰수일까? 맞다. 7을 출력한다. 

마지막 숫자 7은 마지막 숫자이므로 오큰수를 찾을 수 없다. 따라서 -1을 출력한다. 

 

이제 이걸 코드로 옮겨보자. 

 

 

코드 1 - 오답

using System.Text;

namespace 스택
{
    internal class BOJ17298_오큰수
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
            Stack<int> stack = new Stack<int>();

            int N = int.Parse(sr.ReadLine());

            string[] input = sr.ReadLine().Split(" ");
            int[] intArray = new int[input.Length];
            for(int i = 0; i < input.Length; i++)
            {
                intArray[i] = int.Parse(input[i]);
            }

            int targetNumber = 0;
            int index = 0;
            for (int i = 0; i < input.Length; i++)
            {
                targetNumber = intArray[i];
                index = i;
                if (i == 0)
                {
                    stack.Push(targetNumber);
                    continue;
                }

                // input[i](=targetNumber)가 stack.Peek의 오큰수인가? ( targetNumber > stack.Peek() )
                if (targetNumber > stack.Peek())
                {
                    stack.Pop();
                    sb.Append(targetNumber + " ");

                    stack.Push(targetNumber);

                    continue;
                }

                // 오큰수가 아니면 
                while(targetNumber <= stack.Peek())
                {
                    index++;
                    if (index >= intArray.Length) break;
                    targetNumber = intArray[index];

                    // 오큰수이면
                    if(targetNumber > stack.Peek())
                    {
                        stack.Pop();
                        sb.Append(targetNumber + " ");

                        stack.Push(intArray[i]);

                        break;
                    }
                }

                if(index >= intArray.Length)
                {
                    stack.Pop();
                    sb.Append(-1 + " ");

                    stack.Push(intArray[i]);
                }
            }

            sb.Append(-1 + " ");

            sw.WriteLine(sb.ToString());

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

 

시간 초과로 오답처리가 되었다. 

왜일까.. 

 

 

코드 2 - 오답

using System.Text;

namespace 스택
{
    internal class BOJ17298_오큰수
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();

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

            int N = int.Parse(sr.ReadLine());

            string[] input = sr.ReadLine().Split(" ");
            int[] intArray = new int[input.Length];
            for (int i = 0; i < input.Length; i++)
            {
                intArray[i] = int.Parse(input[i]);

                if(i == 0)
                {
                    stack.Push(intArray[i]);
                }
            }

            for(int i = 1; i < intArray.Length; i++)
            {
                // intArray[i]가 stack.Peek의 오큰수이면 
                if (intArray[i] > stack.Peek())
                {
                    // 오큰수를 찾았으면 
                    // 그 숫자를 출력하고
                    // 스택에는 오큰수를 찾은 숫자를 삭제한다. 
                    sb.Append(intArray[i]);
                    stack.Pop();
                }
                // intArray[i]가 stack.Peek의 오큰수가 아니면 
                else
                {
                    // i+1번쨰는 stack.Peek의 오큰수가 아닌지 비교한다. 
                    // 결국에는 i+1, i+2를 비교하고 있으니 이것도 O(N^2) 풀이다. 시간초과가 난다. 
                }
            }
        }
    }
}

 

코드를 적다보니 이 코드도 결국에는 시간복잡도가 O(N^2)가 되고 있었다. 

더 할 것도 없었다. O(N^2) 코드는 시간 초과가 나니 잘못된 코드다. 

 

 

코드 3 - 정답

namespace 스택
{
    internal class BOJ17298_오큰수
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int[] array = new int[1000000];
            int[] answer = new int[1000000];

            int n = int.Parse(sr.ReadLine());

            string[] input = sr.ReadLine().Split(" ");
            for(int i = 0; i < n; i++)
            {
                array[i] = int.Parse(input[i]);
            }

            Stack<int> stack = new Stack<int>();
            for(int i = n - 1; i >= 0; i--)
            {
                while(stack.Count > 0 && stack.Peek() <= array[i])
                {
                    stack.Pop();
                }

                if(stack.Count == 0)
                {
                    answer[i] = -1;
                }
                else
                {
                    answer[i] = stack.Peek();
                }

                stack.Push(array[i]);
            }

            for(int i = 0; i < n; i++)
            {
                sw.Write($"{answer[i]} ");
            }

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

 

정답 코드다. 

수열의 젤 끝 숫자를 스택에 넣고 빼는 풀이다. 

눈으로 보고 이해는 했으나 어떻게 이렇게 풀 생각을 했을까 싶다. 

꼭 for문을 앞에서부터 돌아야 한다는 고정관념을 없애야 겠다.