[Kotlin] Korean Coding Test - Programmers - Desktop Organization

Question

Link

As he prepares for the coding test, he solves the problem in Programmer's and saves the code he wrote to study it again on his computer desktop. As the number of saved codes increased, he thought his computer desktop was too messy. I decided to delete all the saved files because the code I wrote in Programmer's can go and see it again in the problem.

The computer desktop is a grid in which each space is a square. At this point, you will be given a string array wallpaper that shows the status of your computer's desktop. The files are located in the grid compartment of the desktop, and the grid points on the desktop represent the top left of the desktop starting with (0, 0) (vertical coordinates, horizontal coordinates). Blank has a value of "." and file has a value of "#." Drag to select files and delete selected files. Embarrassed wants to select and erase all files at once with one drag with minimal travel distance, and here's how to select files with drag.

• Drag is the action of moving to grid point E (rdx, rdy) with the left mouse click on the grid point S (lux, luy) on the desktop and releasing the left mouse button. At this time, express "drag from point S to point E" and express point S and point E as the starting point and end point of the drag, respectively.
• When dragging from point S (lux, luy) to point E (rdx, rdy), the "dragged distance" is defined as |rdx - lux| + |rdy - luy|.
• Drag from point S to point E selects all files inside a rectangle with two grid points on the desktop, up left and down right, respectively.

Write a solution function that returns an integer array containing the starting and ending points of a drag with a minimum travel distance to delete files on the desktop when a wallpaper is given as a parameter. If the drag starts at (lux, luy) and ends at (rdx, rdy), you can return the integer array [lux, luy, rdx, rdy].

Restrictions

wallpaper

• 1 ≤ length of wallpaper ≤ 50
• 1 ≤ length of wallpaper [i] ≤ 50
• All elements of the wallpaper are the same length.
• wallpaper[i][j] shows the status of the columns corresponding to i + 1 row j + 1 column on the desktop.
• wallpaper[i][j] has only "#" or "."

There is at least one file on the desktop.

Drag starting points (lux, luy) and ending points (rdx, rdy) must satisfy lux < rdx, luy < rdy.

Input/Output Example

Input/Output Example #1

• Input: [".#...", "..#..", "...#."]
• Output: [0, 1, 3, 4]

Input/Output Example #2

• Input: ["..........", ".....#....", "......##..", "...##.....", "....#....."]
• Output: [1, 3, 5, 8]

Input/Output Example #3

• Input: [".##...##.", "#..#.#..#", "#...#...#", ".#.....#.", "..#...#..", "...#.#...", "....#...."]
• Output: [0, 0, 7, 9]

Input/Output Example #4

• Input: ["..", "#."]
• Output: [1, 0, 2, 1]

Code 1

class Solution {
    fun solution(wallpaper: Array<String>): IntArray {
        val yCount = wallpaper.size
        val xCount = wallpaper[0].length

        var min = Pair(yCount - 1, xCount - 1)
        var max = Pair(0, 0)
        for (y in wallpaper.indices) {
            for (x in 0 until xCount) {
                if (wallpaper[y][x] == '#') {
                    if (y < min.first) min = Pair(y, min.second)
                    if (x < min.second) min = Pair(min.first, x)
                    if (y > max.first) max = Pair(y, max.second)
                    if (x > max.second) max = Pair(max.first, x)
                }
            }
        }
        return intArrayOf(min.first, min.second, max.first + 1, max.second + 1)
    }
}

TEST 1 〉	Pass (0.28ms, 62.6MB)
TEST 2 〉	Pass (0.32ms, 60.6MB)
TEST 3 〉	Pass (0.26ms, 61.2MB)
TEST 4 〉	Pass (0.31ms, 62.1MB)
TEST 5 〉	Pass (0.40ms, 59.1MB)
TEST 6 〉	Pass (0.26ms, 62MB)
TEST 7 〉	Pass (0.40ms, 62.5MB)
TEST 8 〉	Pass (0.41ms, 61.6MB)
TEST 9 〉	Pass (0.80ms, 60.5MB)
TEST 10 〉	Pass (0.35ms, 62.3MB)
TEST 11 〉	Pass (0.39ms, 62MB)
TEST 12 〉	Pass (0.42ms, 61.2MB)
TEST 13 〉	Pass (0.33ms, 62.6MB)
TEST 14 〉	Pass (0.42ms, 60.9MB)
TEST 15 〉	Pass (0.36ms, 60.8MB)
TEST 16 〉	Pass (0.35ms, 61.8MB)
TEST 17 〉	Pass (0.48ms, 61.2MB)
TEST 18 〉	Pass (0.40ms, 61.8MB)
TEST 19 〉	Pass (0.44ms, 61.5MB)
TEST 20 〉	Pass (0.71ms, 60MB)
TEST 21 〉	Pass (0.27ms, 62.1MB)
TEST 22 〉	Pass (0.27ms, 61MB)
TEST 23 〉	Pass (0.28ms, 61.3MB)
TEST 24 〉	Pass (0.37ms, 62.2MB)
TEST 25 〉	Pass (0.36ms, 62.3MB)
TEST 26 〉	Pass (0.41ms, 61.6MB)
TEST 27 〉	Pass (0.29ms, 62.1MB)
TEST 28 〉	Pass (0.45ms, 61.6MB)
TEST 29 〉	Pass (0.47ms, 63.1MB)
TEST 30 〉	Pass (0.74ms, 59.7MB)
TEST 31 〉	Pass (0.36ms, 60.7MB)

Code 2. Utilization of built-in functions

import java.lang.Integer.max
import java.lang.Integer.min

class Solution {
    fun solution(wallpaper: Array<String>): IntArray {
        val yCount = wallpaper.size
        val xCount = wallpaper[0].length

        var (yMin, xMin) = (yCount - 1 to xCount - 1)
        var (yMax, xMax) = (0 to 0)
        for (y in wallpaper.indices) {
            for (x in 0 until xCount) {
                if (wallpaper[y][x] == '#') {
                    yMin = min(y, yMin)
                    xMin = min(x, xMin)
                    yMax = max(y, yMax)
                    xMax = max(x, xMax)
                }
            }
        }
        return intArrayOf(yMin, xMin, yMax + 1, xMax + 1)
    }
}

TEST 1 〉	Pass (0.73ms, 59.2MB)
TEST 2 〉	Pass (0.68ms, 60MB)
TEST 3 〉	Pass (0.46ms, 62.3MB)
TEST 4 〉	Pass (0.47ms, 61.7MB)
TEST 5 〉	Pass (0.51ms, 61.7MB)
TEST 6 〉	Pass (0.46ms, 61.4MB)
TEST 7 〉	Pass (0.53ms, 62MB)
TEST 8 〉	Pass (0.87ms, 61.3MB)
TEST 9 〉	Pass (1.08ms, 60MB)
TEST 10 〉	Pass (0.57ms, 60.5MB)
TEST 11 〉	Pass (0.66ms, 61.2MB)
TEST 12 〉	Pass (0.78ms, 61.5MB)
TEST 13 〉	Pass (0.47ms, 59.7MB)
TEST 14 〉	Pass (0.71ms, 60.2MB)
TEST 15 〉	Pass (0.68ms, 61.6MB)
TEST 16 〉	Pass (0.88ms, 62.1MB)
TEST 17 〉	Pass (0.67ms, 59.3MB)
TEST 18 〉	Pass (0.60ms, 60.1MB)
TEST 19 〉	Pass (0.83ms, 61.2MB)
TEST 20 〉	Pass (0.73ms, 61.4MB)
TEST 21 〉	Pass (0.45ms, 61.9MB)
TEST 22 〉	Pass (0.67ms, 61.7MB)
TEST 23 〉	Pass (0.54ms, 59.5MB)
TEST 24 〉	Pass (0.44ms, 61.1MB)
TEST 25 〉	Pass (0.88ms, 61MB)
TEST 26 〉	Pass (0.90ms, 60.6MB)
TEST 27 〉	Pass (0.57ms, 61.7MB)
TEST 28 〉	Pass (0.58ms, 62.4MB)
TEST 29 〉	Pass (0.54ms, 62MB)
TEST 30 〉	Pass (0.79ms, 61.8MB)
TEST 31 〉	Pass (0.51ms, 62.2MB)

Code 3. Use list sorting

class Solution {
    fun solution(wallpaper: Array<String>): IntArray {
        val map = mutableListOf<Pair<Int, Int>>()

        for (y in wallpaper.indices) {
            for (x in 0 until wallpaper[0].length) {
                if (wallpaper[y][x] == '#') {
                    map.add(Pair(y, x))
                }
            }
        }

        val ySortedMap = map.sortedBy { it.first }
        val xSortedMap = map.sortedBy { it.second }
        return intArrayOf(
            ySortedMap.first().first,
            xSortedMap.first().second,
            ySortedMap.last().first + 1,
            xSortedMap.last().second + 1
        )
    }
}

TEST 1 〉	Pass (28.59ms, 63.4MB)
TEST 2 〉	Pass (17.91ms, 63.8MB)
TEST 3 〉	Pass (23.09ms, 63.5MB)
TEST 4 〉	Pass (20.25ms, 63.4MB)
TEST 5 〉	Pass (17.93ms, 63.8MB)
TEST 6 〉	Pass (20.46ms, 64.5MB)
TEST 7 〉	Pass (31.97ms, 63.5MB)
TEST 8 〉	Pass (20.66ms, 64.7MB)
TEST 9 〉	Pass (35.47ms, 65.2MB)
TEST 10 〉	Pass (25.70ms, 63.9MB)
TEST 11 〉	Pass (21.01ms, 63.5MB)
TEST 12 〉	Pass (24.09ms, 63.1MB)
TEST 13 〉	Pass (18.18ms, 64.1MB)
TEST 14 〉	Pass (24.74ms, 64.4MB)
TEST 15 〉	Pass (17.37ms, 63.3MB)
TEST 16 〉	Pass (17.00ms, 63.4MB)
TEST 17 〉	Pass (23.02ms, 65.5MB)
TEST 18 〉	Pass (19.49ms, 63.4MB)
TEST 19 〉	Pass (18.75ms, 63.9MB)
TEST 20 〉	Pass (25.74ms, 64MB)
TEST 21 〉	Pass (19.03ms, 64.1MB)
TEST 22 〉	Pass (25.72ms, 63.7MB)
TEST 23 〉	Pass (28.70ms, 63.9MB)
TEST 24 〉	Pass (19.58ms, 64.4MB)
TEST 25 〉	Pass (18.57ms, 63.5MB)
TEST 26 〉	Pass (24.57ms, 63.4MB)
TEST 27 〉	Pass (21.75ms, 63.5MB)
TEST 28 〉	Pass (26.93ms, 64MB)
TEST 29 〉	Pass (20.68ms, 64.6MB)
TEST 30 〉	Pass (21.62ms, 63.5MB)
TEST 31 〉	Pass (8.25ms, 62.8MB)

Code 4

class Solution {
    fun solution(wallpaper: Array<String>): IntArray {
        val yCount = wallpaper.size
        val xCount = wallpaper[0].length

        var answer = intArrayOf(yCount, xCount, 0, 0)

        for (y in wallpaper.indices) {
            for (x in 0 until xCount) {
                if (wallpaper[y][x] == '#') {
                    if (answer[0] > y) answer[0] = y
                    if (answer[1] > x) answer[1] = x
                    if (answer[2] < y + 1) answer[2] = y + 1
                    if (answer[3] < x + 1) answer[3] = x + 1
                }
            }
        }

        return answer
    }
}

TEST 1 〉	Pass (0.03ms, 58.5MB)
TEST 2 〉	Pass (0.02ms, 61.2MB)
TEST 3 〉	Pass (0.02ms, 61.9MB)
TEST 4 〉	Pass (0.03ms, 61MB)
TEST 5 〉	Pass (0.02ms, 61.7MB)
TEST 6 〉	Pass (0.03ms, 60.7MB)
TEST 7 〉	Pass (0.06ms, 58.6MB)
TEST 8 〉	Pass (0.09ms, 60.1MB)
TEST 9 〉	Pass (0.17ms, 59.4MB)
TEST 10 〉	Pass (0.05ms, 59.3MB)
TEST 11 〉	Pass (0.05ms, 59.6MB)
TEST 12 〉	Pass (0.05ms, 61.1MB)
TEST 13 〉	Pass (0.05ms, 58.4MB)
TEST 14 〉	Pass (0.05ms, 59.1MB)
TEST 15 〉	Pass (0.09ms, 58.8MB)
TEST 16 〉	Pass (0.16ms, 59.1MB)
TEST 17 〉	Pass (0.04ms, 58.6MB)
TEST 18 〉	Pass (0.15ms, 60.9MB)
TEST 19 〉	Pass (0.09ms, 57.9MB)
TEST 20 〉	Pass (0.11ms, 58.5MB)
TEST 21 〉	Pass (0.06ms, 64.2MB)
TEST 22 〉	Pass (0.03ms, 60.8MB)
TEST 23 〉	Pass (0.03ms, 61.8MB)
TEST 24 〉	Pass (0.03ms, 59.2MB)
TEST 25 〉	Pass (0.12ms, 61.7MB)
TEST 26 〉	Pass (0.11ms, 60.1MB)
TEST 27 〉	Pass (0.07ms, 61MB)
TEST 28 〉	Pass (0.05ms, 60.2MB)
TEST 29 〉	Pass (0.04ms, 61.5MB)
TEST 30 〉	Pass (0.13ms, 61.9MB)
TEST 31 〉	Pass (0.08ms, 60.9MB)