백준 2493 탑 - [알고리즘] [kotlin]

문제 내용

문제 분석

1. 높이가 서로 다른 탑 N개가 일직선상에 있다.

2. 각 탑은 꼭대기에서 레이저를 발사한다.

3. 이때 발사 방향은 왼쪽이다.

4. 더 레이저는 더 높은 탑을 만나면 해당 탑에 수신된다.

5. 각 탑에서 발사한 레이저가 어느 탑에 닿는지 출력하자.

6. 어느 탑에도 닿지 않으면 0을 출력한다.

 

아이디어

1. 문제를 재해석하면 각 탑의 왼쪽 중 본인보다 높은 가장 가까운 탑을 고르는 문제가 된다.

2. 왼쪽 영역에서만 찾아야 하므로 정렬해서는 안된다.

3. bruteFore하게 매번 검사할 시 O(n^2)의 시간 복잡도를 가지므로n = 500000인 상황에서 1.5초안에 해결하기 어렵다.

4. 각 검사마다의 worst case는 더 높은 탑이 없어 왼쪽의 모든 탑을 검사하는 경우이며, 일반화하면 최초로 닿는 탑이 왼쪽에 많이 붙을수록 시간이 많이 걸린다고 볼 수 있다.

5. 수신하는 탑을 고를 때 본인보다 높은 탑이라는 조건 뿐만 아니라, 왼쪽으로 가장 가까운 탑이라는 조건이 붙기 때문에, 이분탐색 등으로 검색하는 시간을 줄일 수 없다.

즉, 검사를 효율적으로 하는 방식이 아닌, 검사할 리스트의 수를 줄이는 방식을 선택해야 한다.

6. 만약 왼쪽의 있는 모든 탑들보다 높은 탑이 있다면, 그 탑 왼쪽의 탑들에게는 레이저가 갈 수 없으므로 검사하지 않아도 무관하다.

일반화하면, 본인의 오른쪽에 본인보다 더 큰 탑이 있다면 본인에게는 앞으로 레이저가 오지 않는다.

7. 즉, 어떤 탑의 왼쪽을 검사할 때 수신한 높은 탑과 본인탑 사이에 있는 탑들은 앞으로의 검사에서 무시해도 무관하다.

8. 검사하려는 탑에서 가장 가까운 탑부터 검사해야 하므로 Stack을 사용하여 검사한다.

9. 본인보다 높은 탑이 나올때까지 기존에 나왔던 탑들을 제거하여 7번의 논리를 구현한다.

10. 이때 탑들의 번호를 알기위해 구조체를 선언하여 사용한다.

 

시간 복잡도

- Stack의 원소 개수가 가장 큰 경우는 조금씩 작은 건물들이 나와 모든 건물이 stack에 있는 경우이다.

이럴 경우 1번의 비교만 수행하므로 O(n)의 시간 복잡도를 갖는다.

 

- 매번 혹은 중간중간 Pop이 일어나는 경우라 할지라도 총 개수인 n개보다 더 많은 pop을 할 수 없다.

이런 경우도 빅오 표기법으로 O(n)의 시간 복잡도를 갖는다.

 

풀이 

import java.util.LinkedList

fun main() {

    data class Top(val height: Int, val num: Int)

    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val tops = br.readLine().split(' ').mapIndexed { index, s -> Top(s.toInt(), index+1) }

    val stack = LinkedList<Top>().apply {
        // 수신하는 탑이 없을 경우 0을 출력해야 한다.
        // 최대 높이의 0번 탑을 가상으로 세워 0이 출력되게 한다.
        addLast(Top(Int.MAX_VALUE,0))
    }

    fun push(top: Top): Int{
        // 본인의 레이저를 수신 가능한 탑을 찾을때까지 pop한 후 push한다.
        // 수신 가능한 탑의 번호를 return한다.
        // 가상의 거대한 탑을 넣었기 때문에 수신 가능한 탑이 없는 경우는 고려하지 않아도 무관하다.
        while (stack.last.height <= top.height) {
            stack.removeLast()
        }
        val resultNum = stack.last.num
        stack.addLast(top)
        return resultNum
    }

    val sb = StringBuilder()
    tops.forEach {
        val result = push(it)
        sb.append("$result ")
    }

    print(sb.toString())
}