02/15 알고리즘 공부(48) - K번째

조건

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

알고리즘 예상

1. array 가운데 부분을 자른다.(or 왼쪽 오른쪽 자르고 합치기)
2. 정렬하기(sorted)
3. k번째 수 가져오기
4. 반복해서 answer에 저장하기

 

초기 코드

class Solution {
    fun solution(array: IntArray, commands: Array<IntArray>): IntArray {
        var answer = intArrayOf()
        return answer
    }
}

 

내 코드

class Solution {
    fun solution(array: IntArray, commands: Array<IntArray>): IntArray {
        var answer = intArrayOf()
        var newArray = intArrayOf()
        for (i in commands){
            newArray = array.slice(i[0]-1..i[1]-1)
            answer += newArray.sorted()[i[2]-1]
        }
        return answer
    }
}

최적화를 한번 해보겠다.

class Solution {
    fun solution(array: IntArray, commands: Array<IntArray>): IntArray {
        var answer = intArrayOf()
        for (i in commands){
            answer += array.slice(i[0]-1..i[1]-1).sorted()[i[2]-1]
        }
        return answer
    }
}

for문을 없에고 forEach나 map을 이용해도 될 것 같다.

class Solution {
    fun solution(array: IntArray, commands: Array<IntArray>): IntArray = commands.map { array.slice(it[0]-1..it[1]-1).sorted()[it[2]-1] }.toIntArray()
}

다른 사람의 풀이

class Solution {
        fun solution(array: IntArray, commands: Array<IntArray>): IntArray {
            return commands.map { command ->
                array.slice(IntRange(command[0] - 1, command[1] - 1)).sorted()[command[2] - 1]
            }
                .toIntArray()
        }
    }

개선점 또는 배운점

1. 코드블럭이 없더라도 줄 구분을 해야겠다.
2. 여기도 있다구요

 

개선된 코드

class Solution {
    fun solution(array: IntArray, commands: Array<IntArray>): IntArray = commands.map {
        array.slice(it[0]-1..it[1]-1).sorted()[it[2]-1] 
    }.toIntArray()
}