K번째수 (Java)

https://programmers.co.kr/learn/courses/30/lessons/42748

코딩테스트 연습 - K번째수

 

프로그래머스 코딩테스트 고득점 Kit 정렬 K번째수 문제 풀이이다.

배열에서 i번째부터 j번째까지 추출하고 정렬한 후 k번째 값을 찾으면되는 로직이 간단한 문제였다.

 

# 1

첫 번째 풀이는 단순히 반복문 만을 이용하여 배열의 일부를 추출하는 방법으로 풀었다.

* Arrays.copyOfRange(array, i, j) 처럼 일부를 배열로 반환하는 메소드를 사용하자.

 

import java.util.Collections;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for (int idx = 0; idx < commands.length; idx++) {
            int i = commands[idx][0];
            int j = commands[idx][1];
            int k = commands[idx][2];
            
            List<Integer> targetList = new ArrayList<>();
            for (int temp = i - 1; temp < j; temp++) {
                targetList.add(array[temp]);
            }
            Collections.sort(targetList);
            
            answer[idx] = targetList.get(k-1);
        }
        return answer;
    }
}

 

테스트 결과

 

# 2

두 번째 풀이는 배열을 추출하고 정렬하는 것까지 모두 스트림을 활용한 코드이다.

 

import java.util.Collections;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for (int idx = 0; idx < commands.length; idx++) {
            int i = commands[idx][0];   // i번째 숫자부터
            int j = commands[idx][1];   // j번째 숫자까지 자르고
            int k = commands[idx][2];   // k번째에 있는 수 구하기
            
            answer[idx] = Arrays.stream(array, i-1, j)
                            .boxed()    // 원시타입을 클래스타입으로 변환
                            .sorted()   // 정렬
                            .collect(Collectors.toList())   // 스트림을 리스트로 변환
                            .get(k-1);  // 리스트의 n번째 요소 가져오기
        }
        return answer;
    }
}

 

테스트 결과

코드는 단순해졌지만 스트림도 내부적으로는 반복문으로 구성되어 있어 시간이 오래 걸린다. 또, 배열을 리스트로 변환하지 않고 원시 타입을 사용하면 시간을 더 단축할 수 있다.