[백준 문제풀기] #2493번 - 탑 with Kotlin

💡문제 

 

💁🏻‍♀️How to Solve

처음에 풀었던 방법은 시간초과가 났다..

 시간복잡도를 다시 생각해보니 내가 짠 로직은 O(n^2)가 발생하여 시간초과가 난다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.Stack

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val input = readLine().toInt()
    val st = readLine().split(" ")
    val stack = Stack<Int>()
    val sb = StringBuffer()

    for (i in st){
        stack.add(i.toInt())
    }

    repeat(input){
        val height = stack.pop()

        var i = stack.size - 1

        while(true){
            if(i < 0 ){
                sb.append(0 )
                break
            }
            if(height < stack[i]){
                sb.append("${i+1} ")
                break
            }
            else{
                if( i == 0 ){
                    sb.append("0 ")
                    break
                }
                else{
                    i -= 1
                }
            }
        }
    }

    for (i in sb.length - 1 downTo 0) {
        print(sb[i])
    }
}

 

구글링하여 다른 분꺼 참고하여 이해하였다..

나는 예를 들어 6 9 5 7 4이렇게 들어오면 스택에 저장한 뒤 , 뒤에(9)부터 비교해가며 풀었는데 이 풀이는 앞에서부터 비교해갔다.

 

먼저, ArrayDeque<Pair<현재 높이, 몇 번째 위치>>() 를 생성하여 위치정보를 같이 담을 수 있도록 한다.

5
6 9 5 7 4 이렇게 들어오면 6부터 차례대로 비교해간다.

초기에는 아직 탑의 정보가 없으므로 제일 높은 탑을 max = 0 이라고 설정해두고 푼다.

 

만약 들어온 값(6)이 max(0)보다 크면 왼쪽방향으로 수신받을 수 있는 값이 없다는 것이다.

따라서 0을 stringBuilder()에 넣어준다.

 

그 후 max값보다 큰 현재 높이로 max를 설정해둔다. 

 

다음으로 들어온 숫자는 9이다. 

9와 max값(6)을 비교해봤을 때도 현재 탑의 높이가 더 높다. 따라서 0을 넣어준다.

 

그다음 탑의 높이 5와 max값 9를 비교해봤을 때 max값이 더 크다. 

즉, 5에서 발사한 레이저 신호를 받을 탑이 왼쪽에 있다는 것이다. 

 

이때 왼쪽 방향으로 하나씩 확인해가며 받을 수 있는 제일 가까운 탑을 찾아야하므로, 마지막에서부터 하나씩 확인하며 5보다 큰 값이라면 해당 탑의 위치 정보를 str에 넣어주고, 아니라면 arr에 있는 마지막 탑을 지우고 그 다음 탑과 비교해간다. 

 

반복하여 str에 저장된 값을 출력해준다. 

 

fun main() {
    with(java.io.StreamTokenizer(System.`in`.bufferedReader())) {
        val str = StringBuilder()
        val arr = ArrayDeque<Pair<Int, Int>>()
        var max = 0
        fun num(): Int {
            nextToken()
            return nval.toInt()
        }
        repeat(num()) {
            num().let { num ->
                if (max < num){ // 제일 높은 탑이 현재 탑보다 낮음 -> 수신하는 탑 없음
                    str.append(0)
                    arr.clear()
                    arr.addLast(Pair(num, it + 1))
                    max = num
                }
                else { // 제일 높은 탑이 현재 탑보다 높음 -> 수신하는 탑 있음
                    while (true){ // 낮은 탑들을 peek에서부터 제거해 나감
                        if (arr.last().first < num){ // 낮은 탑을 지움
                            arr.removeLast()
                        }
                        else { // 높은 탑 -> 수신하는 탑에 도달
                            str.append(arr.last().second)
                            arr.addLast(Pair(num, it + 1))
                            break
                        }
                    }
                }
                str.append(' ')
            }
        }
        print(str)
    }
}