[알고리즘]프로그래머스 42748번 - K번째수

프로그래머스 42748번 - K번째수

프로그래머스 42748번 - https://programmers.co.kr/learn/courses/30/lessons/42748

요구사항

1. 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬

2. 정렬된 배열에서 k번째 있는 수를 구하자.

요구사항 분석 및  풀이과정

i번째 숫자부터 j번째 숫자까지 정렬을 한 후, 정렬된 배열에서 k번째 있는 수를 구하는 것이다. i와 j는 변하므로 배열 array를 한번 정렬해두고 재사용은 하지 못한다. 매번 배열 array의 i번째 숫자부터 j번째 숫자까지에 대해서 정렬을 수행한 후 k번째 있는 수를 구하면 된다.

 

배열 array의 i번째 숫자부터 j번째 숫자까지를 뽑아내기 위하여 Arrays.copyOfRange(src, from, to) 메서드를 사용하면 편하다. 주의하여야 하는 점은 from은 inclusive(포함), to는 exclusive(미포함)이라는 점이다.

 

정렬은 기본자료형에 대해서 정렬을 할 것이므로 Arrays.sort 메서드를 사용하면 된다. 만약 기본자료형의 래퍼 클래스에 대해서 정렬을 하고 싶다면 Collections.sort 메서드를 사용하면 된다.

소스코드 작성

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] result = new int[commands.length];
        
        for(int idx = 0; idx < commands.length; idx++) {
            int i = commands[idx][0], j = commands[idx][1], k = commands[idx][2];
            int[] sub = Arrays.copyOfRange(array, i-1, j);
            Arrays.sort(sub);
            result[idx] = sub[k-1];
        }
        
        return result;
    }
}

별해 - 스트림 사용

import java.util.stream.IntStream;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] result = new int[commands.length];
        
        for(int loop = 0 ; loop < commands.length; loop++) {
            int i = commands[loop][0], j = commands[loop][1], k = commands[loop][2];
            result[loop] = IntStream.rangeClosed(i-1, j-1)
                .map(idx -> array[idx])
                .sorted()
                .toArray()[k-1];
        }
        
        return result;
    }
}

결과

기본자료형을 사용해서 매우 빠르다.

결과 - 별해

스트림을 사용해서 그런지 당연히 기본자료형에 비해 속도는 조금 느리지만 충분히 빠른 것 같다.

 

소스코드 깃허브 주소

링크