{"id":35022,"date":"2024-11-01T09:34:44","date_gmt":"2024-11-01T09:34:44","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35022"},"modified":"2024-11-01T11:45:17","modified_gmt":"2024-11-01T11:45:17","slug":"%d0%baotlin-coding-test-course-finding-building-order","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35022\/","title":{"rendered":"\u041aotlin Coding Test Course, Finding Building Order"},"content":{"rendered":"

<\/p>\n

In coding tests, algorithm problems usually involve designing an algorithm to solve a specific problem. In this course, we will tackle the problem titled ‘Finding the Order of Buildings’ using Kotlin.<\/p>\n

Problem Description<\/h2>\n

Given input consists of the height and position of multiple buildings. We need to determine the order in which each building is visible, considering all the given buildings. In other words, we aim to find out how the order is determined when one building is behind another, making it not visible.<\/p>\n

Input Format<\/h3>\n
\n    The first line contains the number of buildings N (1 \u2264 N \u2264 200,000).\n    Then, for N lines, each building's height H (1 \u2264 H \u2264 10^9) and position P (1 \u2264 P \u2264 10^9) are given.\n    <\/code><\/pre>\n
Output Format<\/h3>\n
\n    Output N integers representing the order in which each building is visible.\n    <\/code><\/pre>\n
Problem Solving Approach<\/h2>\n
To solve this problem, we must analyze the relationship between each building’s height and position relative to other buildings. We follow these steps:<\/p>\n
    \n
  1. Sort the provided buildings based on height<\/strong> and position<\/strong>.<\/li>\n
  2. Check each sorted building one by one to determine if it is visible.<\/li>\n
  3. Then, count the number of visible buildings to collect the results.<\/li>\n<\/ol>\n
    Code Implementation<\/h2>\n
    Now, let’s implement the code in Kotlin to solve the problem based on the discussed approach:<\/p>\n
    \n    data class Building(val height: Int, val position: Int)\n\n    fun findVisibleBuildings(buildings: List): List {\n        \/\/ Sort buildings (sorting by height in descending order)\n        val sortedBuildings = buildings.sortedWith(compareByDescending { it.height }.thenBy { it.position })\n        val visibleCount = mutableListOf()\n        \n        var lastHeight = 0\n        \n        for (building in sortedBuildings) {\n            if (building.height > lastHeight) {\n                visibleCount.add(building.position)\n                lastHeight = building.height\n            }\n        }\n        \n        \/\/ Sort to return results in original order\n        return visibleCount.sorted()\n    }\n\n    fun main() {\n        val buildingCount = readLine()!!.toInt()\n        val buildings = mutableListOf()\n        \n        for (i in 0 until buildingCount) {\n            val (height, position) = readLine()!!.split(\" \").map { it.toInt() }\n            buildings.add(Building(height, position))\n        }\n        \n        val result = findVisibleBuildings(buildings)\n        println(result.joinToString(\" \"))\n    }\n    <\/code><\/pre>\n
    Code Explanation<\/h2>\n
    The code above provides comments to explain the flow, but to summarize, it consists of the following steps:<\/p>\n
      \n
    1. Create a Building<\/code> data class to hold the building information.<\/li>\n
    2. Sort the given buildings in descending order of height.<\/li>\n
    3. If the current building’s height is greater than the tallest building checked so far, add its position to visibleCount<\/code>.<\/li>\n
    4. After checking all buildings, return the results sorted in their original order.<\/li>\n<\/ol>\n
      Time Complexity Analysis<\/h2>\n
      The time complexity of this algorithm is O(N log N). This is the sum of the time taken to sort the list of buildings and the time taken to find the tallest building. Therefore, it can efficiently handle large datasets.<\/p>\n
      Conclusion<\/h2>\n
      Through this course, we learned how to solve the ‘Finding the Order of Buildings’ problem using Kotlin. There are various approaches to solving algorithm problems, and understanding and verifying them is crucial. I hope to further enhance coding skills through various problems in the future.<\/p>\n
      Future References<\/h2>\n