백준 17298 오큰수 Kotlin

백준 17298 오큰수

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

문제 내용은 복잡하지 않다.

주어진 정수 배열에서 각 원소의 오른쪽에 있고, 해당 원소보다 큰 원소 중에서 가장 왼쪽에 있는 수를 각각 출력하는 문제이다 (없다면 -1 출력).

예를들어 input으로 [3, 5, 2, 7]이 들어온다면 [5, 7, 7, -1]을 출력하면 된다.

input 배열의 크기는 1~1,000,000이고 각 원소 크기도 1~1,000,000이다.

input 배열의 크기를 보아 O(nlog n) 이내로 알고리즘을 작성해야 할 것 같았으며

배열을 순회하며 특정 원소 위치에 도착했을 때 그 바로 이전의 원소가 현재 원소보다 작을 경우 현재 원소의 위치로부터 이전 원소들을 비교하며 작업하기에 스택이 적합해 보였다.

핵심 풀이 방법

input 배열이 [9, 8, 7, 3, 2, 4, 10]이라고 하자.

출력해야 하는 내용은 [10, 10, 10, 4, 4, 10, -1] 으로, input 배열의 index를 유지해야 함을 알 수 있다.

data class IdxNum(
    val idx: Int,
    val num: Int
)

따라서 인덱스와 숫자를 함께 담을 클래스를 하나 생성하여 활용하였다.

오른쪽에 있는 원소가 현재 인덱스의 원소보다 큰 경우에 현재 인덱스에 대한 결과값을 정할 수 있다.
이를 이용하여 케이스들을 나누면 아래와 같다.

1. 등장한 원소가 이전 구간들과 내림차순을 유지하는 경우
   구간이 내림차순일 경우 현재 위치의 원소보다 큰 원소가 등장하지 않았음을 알 수 있다.
   따라서 해당 원소는 스택에 넣는다.
   (보다 큰 원소인 것이 중요하므로 같은 원소가 등장하더라도 내림차순으로 여긴다)

2. 등장한 원소가 내림차순을 깨는 원소인 경우
   이전 내림차순 구간을 거꾸로 거슬러 가며 등장한 원소보다 작다면 등장한 원소의 값으로 결과 배열을 채운다.

이 케이스들을 [9, 8, 7, 3, 2, 4, 10] 배열에 적용해 보자.

0. input 배열과 동일한 크기의 결과 배열을 만들고 -1로 초기화한다. (따로 -1 넣지 않기 위함)

0	1	2	3	4	5	6
-1	-1	-1	-1	-1	-1	-1

1. 먼저 9, 8, 7, 3, 2는 계속 내림차순 구간이므로 스택에 넣고 넘어간다.
   (Stack 맨 위의 원소와 비교하면 간편하다)

2. 숫자 4가 등장하면 내림차순이 깨지게 된다.

3. 스택에서 원소를 하나씩 꺼내며 숫자 4와 비교하고, 4보다 작은 경우 그 위치에서 결과값이 4가 되도록 결과 배열을 채운다.

   3-1. 스택 맨 위 원소 2가 4보다 작으므로 원소 2를 꺼낸 뒤 원소 2의 결과에 해당하는 인덱스인 4번 위치의 값을 4로 지정한다.
   

0	1	2	3	4	5	6
-1	-1	-1	-1	4	-1	-1

3-2. 다음 맨 위 원소 3이 4보다 작으므로 동일하게 결과 배열 3번 위치의 값을 4로 지정한다

0	1	2	3	4	5	6
-1	-1	-1	4	4	-1	-1

3-3. 다음 맨 위 원소 7은 4보다 크므로 4를 스택에 넣고 내림차순을 유지하며 다음으로 넘어간다.

4. 숫자 10이 등장하면 또다시 내림차순이 깨지므로 3번 과정과 동일하게 스택을 비우며 결과 배열을 채운다.

위 작업을 모두 끝낸 결과 배열은 아래와 같다.

0	1	2	3	4	5	6
10	10	10	4	4	10	-1

위 내용을 구현한 코드입니다.

import java.util.*

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val size = readLine().toInt()
    val num = readLine().split(' ').mapIndexed { idx, s -> IdxNum(idx,s.toInt()) }
    val result = MutableList(num.size){-1}
    val stack = Stack<IdxNum>()

    stack.push(num[0])
    for(i in 1 until num.size){
        if(stack.peek().num >= num[i].num){
            stack.push(num[i])
        }else{
            while(stack.isNotEmpty() && stack.peek().num < num[i].num){
                val pop = stack.pop()
                result[pop.idx] = num[i].num
            }
            stack.push(num[i])
        }
    }

    val answer = StringBuilder()
    for(n in result){
        answer.append("$n ")
    }
    print(answer.toString())
}

data class IdxNum(
    val idx: Int,
    val num: Int
)