[백준] 17298. 오큰수 (Kotlin)

문제

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

17298번: 오큰수

 

풀이

0. 문제 해석

스택을 활용해야 하는 것은 알겠는데 어떻게 사용해야 할지 몰라 헤맨 문제이다.

 

1. 수열을 리스트에 저장한다.
2. 리스트의 첫번째 원소의 인덱스부터 하나하나씩 스택에 인덱스 값을 push한다.
3. 2번 과정에서 push하기 전에, 그 값이 오큰수라면 pop하고 그 pop한 인덱스 값에 해당하는 리스트의 값을 오큰수로 변경해준다.
4. 반복이 종료된 후 스택에 남아있는 인덱스는 오큰수를 찾지 못한 위치이므로 -1로 바꿔준다.

 

https://st-lab.tistory.com/196

이미지로 잘 정리해놓으신 ST 님의 풀이를 참고하였습니다!

1. 전체 코드

// [백준] 17298. 오큰수 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val list = arrayListOf<Int>()
    val stack = Stack<Int>()
    val sb = StringBuilder()

    for(i in 0 until n){
        val next = st.nextToken().toInt()
        list.add(next)
    }

    for(i in 0 until list.size){
        // 스택이 비어있지않고, 오큰수를 찾았을 때 pop 하여 index 값을 오큰수로 변경
        while(stack.isNotEmpty() && list[stack.peek()] < list[i]){
            list[stack.pop()] = list[i]
        }
        stack.push(i) // 인덱스값 push
    }

    // 스택에 남아있는 인덱스는 오큰수를 찾지 못한 것
    while(stack.isNotEmpty()){
        list[stack.pop()] = -1
    }

    for(i in 0 until list.size){
        sb.append("${list[i]} ")
    }

    println(sb)
}

 

 

참고

https://st-lab.tistory.com/196