C# 코딩테스트 강좌, 오큰수 구하기

문제 설명

오큰수(오른쪽 큰 수) 문제는 배열에서 각 원소에 대해 오른쪽에 있는 원소 중에서 자기보다 큰 수를 찾는 것입니다.
주어진 배열에서 각 원소에 대해 그 원소 오른편에 위치한 원소 중 자기보다 더 큰 수가 있는 경우,
그 수를 결과로 반환하고, 그러한 수가 없다면 -1을 반환합니다.

예시

예를 들어, 배열이 [3, 5, 2, 7]인 경우:

3의 오른쪽 큰 수는 5 입니다.
5의 오른쪽 큰 수는 7 입니다.
2의 오른쪽 큰 수는 7 입니다.
7의 오른쪽 큰 수는 없습니다. 따라서 -1 입니다.

따라서 결과는 [5, 7, 7, -1]가 됩니다.

문제 접근 방법

이 문제를 해결하기 위해서는 효율적인 알고리즘이 필요합니다. 단순히 이중 루프를 사용할 경우 시간복잡도가 O(n^2)으로 비효율적입니다.
따라서 스택을 활용한 방법을 사용하면 O(n)으로 처리할 수 있습니다.

스택을 사용하는 이유

스택은 LIFO(Last In First Out) 구조로, 최근에 추가된 데이터를 가장 먼저 꺼내게 됩니다.
이를 활용하여 현재 원소가 스택의 맨 위 원소보다 클 경우, 스택에서 꺼내면서 각 원소의 오큰수를 찾을 수 있습니다.
스택을 사용한 알고리즘이 작동하는 방식은 다음과 같습니다:

알고리즘 단계

결과를 저장할 배열을 초기화한다.
빈 스택을 초기화한다.
원소를 왼쪽에서 오른쪽으로 순회한다.
스택이 비어 있지 않고 현재 원소가 스택의 맨 위 원소보다 크면, 스택에서 원소를 꺼내고 해당 원소의 오큰수를 현재 원소로 설정한다.
현재 원소의 인덱스를 스택에 추가한다.

코드 구현

이제 위에서 설명한 알고리즘을 C#으로 구현해 보겠습니다. 아래는 전체 코드입니다:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int[] arr = { 3, 5, 2, 7 };
        int[] result = FindNextGreater(arr);
        Console.WriteLine(string.Join(", ", result)); // Output: 5, 7, 7, -1
    }

    static int[] FindNextGreater(int[] arr)
    {
        int n = arr.Length;
        int[] result = new int[n];
        Stack stack = new Stack();

        for (int i = 0; i < n; i++)
        {
            while (stack.Count > 0 && arr[stack.Peek()] < arr[i])
            {
                result[stack.Pop()] = arr[i];
            }
            stack.Push(i);
        }

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

        return result;
    }
}

코드 설명

위 코드의 각 부분을 자세히 살펴보겠습니다.

변수 설정: 주어진 입력 배열 arr의 길이를 n에 저장하고, 결과를 저장할 result 배열과 스택을 초기화합니다.
메인 루프: 원소를 순회하며 스택에 저장된 인덱스의 원소가 현재 원소보다 작은 경우, result 배열에 현재 원소를 설정하고 스택에서 그 인덱스를 제거합니다.
스택 업데이트: 현재 원소의 인덱스를 스택에 추가합니다.
잔여 스택 처리: 스택에 남아 있는 인덱스는 오른쪽에 더 큰 수가 없으므로 모두 -1로 설정합니다.

결론

오큰수를 찾는 문제는 스택을 활용하여 효율적으로 해결할 수 있는 좋은 예입니다.
코딩 테스트에서 이러한 문제를 접했을 때는 스택이나 큐와 같은 자료 구조를 적극 활용해 보세요.
다양한 문제를 풀어보면서 손에 익히는 것이 중요합니다.

추가 연습 문제

다른 모든 원소에 대해 왼쪽 큰 수를 찾는 문제를 해결해 보세요.
오큰수를 구하는 방법을 다양한 데이터 유형(예: 부동소수점 배열 등)으로 확장해 보세요.

참고 자료

GeeksforGeeks – Next Greater Element
Programiz – C# Arrays

맺음말

알고리즘 문제는 처음에는 어렵게 느껴질 수 있지만, 반복 학습과 연습을 통해 점점 더 익숙해질 수 있습니다.
이 강좌를 통해 오큰수를 구하는 방법을 잘 이해하시기 바랍니다. 다양한 문제를 풀어보시고, 자신만의 코드 스타일을 발전시키세요.