오큰수 C#

📝 문제

 

문제 설명

크기가 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)이 주어진다.

---

입출력 예 설명

예제 입력 1

4
3 5 2 7

예제 출력 1

5 7 7 -1

---

예제 입력 2

4
9 5 4 8

예제 출력 2

-1 8 8 -1

---

첫 번째 풀이 코드 - 시간 초과

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

static void Main(string[] args)
{
    int index = int.Parse(Console.ReadLine());
    int[] nums = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

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

    for (int i = index - 1; i >= 0; i--)
        stack.Push(nums[i]);

    for (int i = 0; i < index; i++)
    {
        int curNum = stack.Pop();

        for (int j = i + 1; j <= index; j++)
        {
            if (j == index)
            {
                anwer.Append("-1" + " ");
                break;
            }

            int temp = nums[j];
            if (curNum < temp)
            {
                anwer.Append(nums[j] + " ");
                break;
            }
        }
    }
    Console.WriteLine(anwer);
}

두 번째 풀이 코드 - 통과

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

static void Main(string[] args)
{
    int n = int.Parse(Console.ReadLine());
    int[] nums = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

    StringBuilder sb = new StringBuilder();
    Stack<(int, int)> stack = new Stack<(int, int)>();
    int[] answerArray = new int[n];

    for (int i = 0; i < n; i++)
    {
        while (stack.Count > 0 && (stack.Peek().Item1 < nums[i]))
        {
            answerArray[stack.Peek().Item2] = nums[i];
            stack.Pop();
        }

        stack.Push((nums[i], i));
    }

    while(stack.Count > 0)
    {
        answerArray[stack.Peek().Item2] = -1;
        stack.Pop();
    }

    answerArray[n - 1] = -1;

    foreach (int answer in answerArray)
        sb.Append(answer + " ");

    Console.WriteLine(sb);
}

• 이 문제를 해석해보면, 단순히 현재 숫자와 다음 숫자들을 비교해 가장 가까운 숫자를 정답에 차곡차곡 넣으면 된다. 현재 숫자보다 큰 수가 없다면 -1을 넣는다.

✍️ 중요 포인트

• 첫 번째 시도는 스택에 입력된 수를 거꾸로 차곡차곡 넣은 후 하나씩 뽑아 전수 검사하는 방식으로 하였다. 결과는 시간복잡도 (N²)가 되어버려 시간초과로 통과하지 못했다.
• 두 번째 시도는 다른 사람 풀이를 보고 나만의 방식으로 수정하였다.
  • 먼저 Stack의 자료형을 튜플을 사용해 (현재 값, 현재값의 인덱스)를 한 번에 저장한다.
  • for문으로 반복해주고, 중간에 조건으로 Stack이 비어있지 않고, 다음에 들어갈 숫자가 현재 스택에 들어있는 숫자보다 크다면 정답 배열에 다음 값을 넣어준다.
    • 정답배열에 넣어줄 때 인덱스는 스택에 저장된 현재값의 인덱스)에 넣어준다.
    • 그리고 Stack의 값을 뽑아준다.