[백준17298번] 오큰수 구하기(C#)

문제

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

 

풀이

처음 문제를 보고 단순하게 생각했다.

1. stack에 array index값을 순서대로 push()
2. 만약 array index값이 array의 길이를 초과하면 pop(), -1 저장
   그리고 stack에 남아있는 값을 모두 pop(), -1 저장
3. (while로 오큰수 찾기

그래서 위와같은 순서를 생각하고 그대로 코드를 작성했다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm
{
    internal class 오큰수
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine()); // 수열의 크기
            int[] array = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); // 수열
            int[] resultArray = new int[N];

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

            for (int i = 0; i < array.Length; i++)
            {
                stack.Push(i); // 패착

                if(i+1 >= array.Length) // 패착
                {
                    stack.Pop();
                    resultArray[i] = -1;
                    
                    while(stack.Count > 0)
                    {
                        int index = stack.Pop();
                        resultArray[index] = -1;
                    }
                }

                int target = array[i+1];
                while(stack.Count > 0) // 패착
                {
                    int top = stack.Peek();

                    if (array[top] < target)
                    {
                        int index = stack.Pop();
                        resultArray[index] = target;
                    }
                    else
                    {
                        break;
                    }
                }

            }

            foreach(int i in resultArray)
            {
                Console.WriteLine(i + " ");
            }
        }
    }
}

디버깅에선 정상적으로 출력되어 바로 문제를 제출하니...

시간 초과가 발생했다. 아무래도 O(n)으로 끝내야 할 연산이 Push()와 while()로 불필요한 연산 과정이 추가되는 듯 했다. 그래서 다음과 같이 개선했다.

1. 스택이 비어있지 않고 && 현재 원소가 스택 top원소보다 클 경우 오큰수 저장
2. 그렇지 않으면 스택에 인덱스 push()

 

기존 코드는 for문의 i를 stack에 담는 용도로 사용했지만, 신규 코드는 for문의 i를 오큰수의 index로 사용했다.

그래서 for문을 돌면서 수를 지정하고, 해당 수를 오큰수로 사용하는 수가 있다면 오큰수를 저장했다.

코드

using System;
using System.Collections.Generic;
using System.Text;

internal class 오큰수
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine()); // 수열 크기
        int[] array = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); // 수열
        int[] resultArray = new int[n]; // 결과 저장 배열
        Stack<int> stack = new Stack<int>(); // 인덱스를 저장할 스택
        StringBuilder sb = new StringBuilder(); // 값을 담을 버퍼

        // 결과 배열을 모두 -1로 초기화
        Array.Fill(resultArray, -1);

        for (int i = 0; i < n; i++)
        {
            // 스택이 비어있지 않고, 현재 원소가 스택 top의 원소보다 클 경우
            while (stack.Count > 0 && array[stack.Peek()] < array[i])
            {
                int index = stack.Pop();
                resultArray[index] = array[i]; // 오큰수 저장
            }

            stack.Push(i); // 현재 인덱스를 스택에 저장
        }

        // 출력
        foreach (var num in resultArray)
        {
            sb.Append(num).Append(' ');
        }
        Console.WriteLine(sb.ToString());
    }
}

반대로 생각하니까 풀렸던 문제다. 그리고 그렇게 복잡하지도 않은건데 내가 너무 많은 경우의 수를 생각해서 if문을 때려박았다. ㅎ... 그냥 오큰수를 정해두고 그거에 부합하는지만 보면 되는거였다.

 

코테는 창의력 테스트같다. ncs 공부하던 ptsd 올라옴