C# 코딩테스트 강좌, 스택으로 오름차순 수열 만들기

문제 설명

주어진 수열에서 스택을 이용하여 오름차순으로 정렬된 수열을 만들 수 있는지 여부를 판단하는 문제입니다. 입력으로 주어진 수열을 스택을 활용하여 가장 작은 수부터 순서대로 출력할 수 있어야 합니다. 만약 불가능한 경우 “NO”, 가능하다면 “YES”를 출력해야 합니다.

문제 예시

입력: 5
입력 수열: 5 1 2 3 4
출력: YES

입력: 7
입력 수열: 1 2 5 3 4 6 7
출력: NO

접근 방법

이 문제는 스택의 특성을 활용하여 해결할 수 있습니다. 스택은 후입선출(LIFO) 구조로, 마지막에 들어온 요소가 가장 먼저 나가는 특성을 가지고 있습니다. 따라서 수열을 오름차순으로 정렬하기 위해서는 입력된 수를 스택에 저장하고, 필요한 경우에만 스택에서 요소를 꺼내어야 합니다.

1단계: 입력 처리

우선 입력으로 주어진 수열을 읽어야 합니다. 수열의 길이와 해당 수열의 원소를 받아옵니다.

2단계: 스택에 요소 저장

입력된 수들을 순차적으로 처리하면서 현재 출력해야 할 수와 비교해야 합니다. 스택을 활용하여 현재 수를 저장하고, 가장 작은 수부터 출력할 수 있도록 합니다.

3단계: 출력 조건 확인

이미 출력해야 할 수보다 큰 수가 스택에 쌓였다면, 해당 수를 더 이상 꺼낼 수 없으므로 “NO”를 출력합니다. 모든 요소를 처리 후 가능한 경우에는 “YES”를 출력합니다.

C# 코드 구현

아래는 위에서 설명한 알고리즘을 C# 언어로 구현한 코드입니다.


using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Stack stack = new Stack();
        int current = 1;

        for (int i = 0; i < n; i++)
        {
            int num = int.Parse(Console.ReadLine());

            while (current <= num)
            {
                stack.Push(current);
                current++;
            }

            if (stack.Count == 0 || stack.Pop() != num)
            {
                Console.WriteLine("NO");
                return;
            }
        }

        Console.WriteLine("YES");
    }
}

코드 설명

위의 C# 코드는 다음과 같이 동작합니다:

int n = int.Parse(Console.ReadLine());
사용자로부터 수열의 길이를 입력받습니다.
Stack stack = new Stack();
스택을 초기화합니다.
int current = 1;
현재 출력해야 하는 수를 나타냅니다.
반복문을 통해 입력된 수 각각에 대해:

while (current <= num)
입력된 수보다 현재 수가 작거나 같을 경우, 현재 수를 스택에 추가하고 현재 수를 증가시킵니다.
if (stack.Count == 0 || stack.Pop() != num)
스택에서 가장 위의 수를 꺼내어 입력된 수와 비교합니다. 만약 스택이 비어있거나 다르다면 “NO”를 출력합니다.

모든 수를 처리한 후에 “YES”를 출력합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 각 수를 한 번씩만 스택에 넣고 빼기 때문입니다. 공간 복잡도 또한 O(n)으로 스택에 최악의 경우 모든 수가 쌓일 수 있습니다.

결론

이 문제는 스택의 특성을 활용하여 해결할 수 있는 전형적인 문제입니다. 코딩 테스트에서는 이러한 스택 문제를 종종 접할 수 있으므로, 스택과 큐의 동작 방식을 충분히 이해하고 있을 필요가 있습니다. 이번 강좌에서는 스택을 사용하여 오름차순으로 수열을 만드는 방법을 배웠습니다. 다양한 문제를 해결하기 위해 이런 기초적인 알고리즘을 연습하는 것이 중요합니다.

추가 연습문제

스택을 이용하여 다른 알고리즘 문제를 풀어보세요:

괄호 균형Checking 문제
후위 표기법 계산기

참고 자료

더 많은 알고리즘을 배우고 싶다면 다음 자료를 참고하세요: