코틀린 코딩테스트 강좌, 빌딩 순서 구하기

코딩 테스트에서 알고리즘 문제는 대개 특정한 문제 해결을 위한 알고리즘을 설계하는 것을 포함합니다. 이 강좌에서는 ‘빌딩 순서 구하기’라는 주제로 Koitlin을 이용하여 문제를 해결해 보겠습니다.

문제 설명

주어진 입력으로 여러 개의 빌딩의 높이와 위치가 들어옵니다. 우리는 주어진 모든 빌딩들을 고려할 때, 각 빌딩이 보이는 순서를 규명해야 합니다. 즉, 어떤 빌딩이 다른 빌딩 뒤에 있을 때, 그 빌딩이 시야에 보이지 않기 때문에 그 순서가 어떻게 결정되는지를 알아내는 것입니다.

입력 형식


    첫 번째 줄에 빌딩의 개수 N (1 ≤ N ≤ 200,000)이 주어진다.
    이후 N개의 줄에 각각의 빌딩의 높이 H (1 ≤ H ≤ 10^9)와 위치 P (1 ≤ P ≤ 10^9)가 주어진다.

출력 형식


    각 빌딩이 시야에 보이는 순서를 나타내는 N개의 정수를 출력한다.

문제 해결 접근 방식

이 문제를 해결하기 위해서는 각 빌딩의 높이와 위치를 기준으로 다른 빌딩과의 관계를 따져야 합니다. 이를 위해 다음과 같은 단계를 따릅니다:

입력된 빌딩의 정보를 바탕으로 각 빌딩을 높이와 위치를 기준으로 정렬합니다.
정렬된 빌딩을 하나씩 확인하면서, 해당 빌딩이 보이는지 확인합니다.
이후, 보이는 빌딩의 수를 카운트하여 결과를 수집합니다.

코드 구현

이제 위의 문제 해결 접근 방식을 바탕으로 코틀린으로 문제를 해결하는 코드를 구현해 보겠습니다:


    data class Building(val height: Int, val position: Int)

    fun findVisibleBuildings(buildings: List): List {
        // 빌딩 정렬 (높이를 기준으로 내림차순 정렬)
        val sortedBuildings = buildings.sortedWith(compareByDescending { it.height }.thenBy { it.position })
        val visibleCount = mutableListOf()
        
        var lastHeight = 0
        
        for (building in sortedBuildings) {
            if (building.height > lastHeight) {
                visibleCount.add(building.position)
                lastHeight = building.height
            }
        }
        
        // 원래 순서로 정렬하여 결과를 반환
        return visibleCount.sorted()
    }

    fun main() {
        val buildingCount = readLine()!!.toInt()
        val buildings = mutableListOf()
        
        for (i in 0 until buildingCount) {
            val (height, position) = readLine()!!.split(" ").map { it.toInt() }
            buildings.add(Building(height, position))
        }
        
        val result = findVisibleBuildings(buildings)
        println(result.joinToString(" "))
    }

코드 설명

위 코드는 주석을 통해 코드의 흐름을 설명하고 있지만 간단하게 요약하자면, 다음과 같은 단계로 이루어집니다:

빌딩의 정보를 담는 Building 데이터 클래스를 생성합니다.
주어진 빌딩들을 높이를 기준으로 내림차순으로 정렬합니다.
높이가 현재까지 확인했던 빌딩들 중에서 가장 높은 빌딩보다 큰 경우, 해당 빌딩의 위치를 visibleCount에 추가합니다.
모든 빌딩을 확인한 후, 원래의 순서대로 정렬하여 결과를 출력합니다.

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N log N)입니다. 이는 빌딩 리스트를 정렬하는 데 드는 시간과 가장 높은 빌딩을 찾는 데 드는 시간의 총합입니다. 따라서 대규모 데이터에서도 효율적으로 동작할 수 있습니다.

결론

이번 강좌를 통해, 코틀린을 사용하여 ‘빌딩 순서 구하기’ 문제를 해결하는 방법에 대해 알아보았습니다. 알고리즘 문제 해결에는 여러 가지 접근 방식이 있을 수 있으며, 이를 규명하고 확인하는 과정이 중요합니다. 앞으로도 다양한 문제를 통해 코딩 실력을 더욱 발전시킬 수 있기를 바랍니다.

차후 참고 자료

감사합니다!