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

문제 설명

주어진 정수 n과 n개의 정수로 이루어진 수열이 있습니다. 당신의 임무는 스택을 이용하여
주어진 수열을 오름차순으로 정렬하는 방법을 구현하는 것입니다. 스택의 특성인 LIFO(Last In, First Out)를 이용해 수열을
처리해야 하며, 스택에 들어갈 최대 개수는 n입니다.

입력 형식

첫 줄에 정수 n (1 ≤ n ≤ 100,000)이 주어집니다.
둘째 줄에 n개의 정수가 공백으로 구분되어 주어지며 (1 ≤ 각 수 ≤ 1,000,000), 수열은 중복될 수 있습니다.

출력 형식

오름차순으로 수열을 정렬하는 과정에서 사용할 수 있는 스택 연산의 과정(푸시, 팝)을 출력합니다.
스택으로 수열을 정렬할 수 없으면 “NO”를 출력해야 합니다.

예제 입력

    5
    4 3 6 8 5

예제 출력

    PUSH 4
    PUSH 3
    POP 3
    PUSH 6
    POP 6
    PUSH 5
    POP 5
    POP 4

문제 풀이

이 문제는 스택을 활용하여 입력된 수열을 오름차순으로 정렬하는 방법을 요구하고 있습니다.
문제를 해결하기 위해 다음의 단계로 접근해보겠습니다.

알고리즘 설계

1. **입력 처리**: 정수 n과 수열을 입력으로 받습니다.
2. **스택 및 출력 리스트 초기화**: 수열을 저장할 리스트, 스택을 초기화합니다.
3. **타겟 값 초기화**: 현재 오름차순에서 나와야 할 다음 타겟 값을 1로 설정합니다.
4. **수열 순회**: 입력된 수열을 순회하며,
– 만약 현재 수가 타겟 값과 같으면 팝 연산을 수행합니다.
– 타겟 값과 다르면 스택에 푸시합니다.
5. **스택 비우기**: 스택에 값이 남아있다면, 이를 팝하여 출력합니다.
6. **출력**: 최종적으로 정렬된 수열을 보여주거나 “NO”를 출력합니다.

코딩 구현

위의 알고리즘을 코틀린으로 구현하면 다음과 같습니다:


fun main() {
    val n = readLine()!!.toInt()
    val sequence = readLine()!!.split(" ").map { it.toInt() }
    val stack = mutableListOf()
    val output = mutableListOf()
    var current = 1
    var index = 0

    while (current <= n) {
        while (index < n && (stack.isEmpty() || stack.last() != current)) {
            stack.add(sequence[index++])
            output.add("PUSH ${stack.last()}")
        }
        if (stack.isNotEmpty() && stack.last() == current) {
            stack.removeAt(stack.size - 1)
            output.add("POP $current")
        } else {
            println("NO")
            return
        }
        current++
    }

    output.forEach { println(it) }
}

주요 고려 사항

이 문제를 푸는 데에 몇 가지 중요한 고려 사항이 있습니다. 우선 스택의 개념을 이해하고
이를 코드로 구현해야 하며, 특정 상황에서 스택을 잘 활용해야 합니다. 또한,
입력된 수가 오름차순으로 정렬되어야 하기 때문에 이를 보장할 수 있는 로직이 필요합니다.
스택의 최대 크기는 n이므로 O(n) 공간 복잡도가 허용됩니다.

결론

이번 강좌에서는 스택을 활용하여 오름차순 수열을 만드는 문제를 다뤘습니다. 기본적인 스택
동작을 이해하고 활용하는 방법을 실제 코드 구현을 통해 확인할 수 있었습니다. 스택이라는 자료구조는 많은 알고리즘 문제에서
다루어지므로, 이 문제를 통해 스택의 활용법을 익혀보길 바랍니다.