[Programmers] K번째수(Java)

이번에는 프로그래머스에서 K번째수 문제를 풀어보았습니다.

주어진 배열에서 특정 범위의 값을 추출한 뒤 오름차순 정렬 후 그 안에서 특정 인덱스의 값이 무엇인지 배열로 반환하는 문제였습니다.

보자마자 Arrays.sort 써야겠다~ 하고 풀었는데 다른 사람의 풀이를 보니 배열 복사관련 Java API인 copyOfRange 쓰는거 보고 머리한대 맞고 댓글에서 정렬 관련해서 Java API 활용해서 풀면 정렬문제가 무슨 소용이냐 직접 정렬을 구현해야지 라는 말을 보고 머리가 두번 깨진 느낌입니다... 일단 다 맞는 말처럼 느껴져서 그냥 다 해버렸습니다.

그래서 직접 구현 버전, 정렬 및 배열복사 관련 Java API를 제대로(?) 활용한 버전, 정렬 알고리즘을 직접 구현한 버전 이렇게 3가지로 풀었고 전체 코드는 아래와 같습니다.

정렬은 퀵 정렬을 사용했고 퀵 정렬이란 피봇이라는 기준 값을 선택하여 배열을 왼쪽과 오른쪽 두 영역으로 분할한 후 재귀적으로 정렬하는 방식으로, 평균적으로 O(n log n)의 시간 복잡도를 가집니다. 구체적인 내용은 코딩하는 거니님의 유튜브를 참고하였습니다.

[직접 구현 버전]

import java.util.*;
public class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for (int cnt = 0; cnt < commands.length; cnt++) {
            int i = commands[cnt][0] - 1, j = commands[cnt][1] - 1, k = commands[cnt][2] - 1;
            int[] targetArr = new int[j - i + 1];
            int targetArrIdx = 0;
            for (int arrIdx = i; arrIdx <= j; arrIdx++) { // 배열 복사
                targetArr[targetArrIdx++] = array[arrIdx];
            }

            Arrays.sort(targetArr);
            answer[cnt] = targetArr[k];
        }

        return answer;
    }
}

[정렬 및 배열복사 관련 Java API를 활용한 버전]

import java.util.*;
public class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for (int i = 0; i < commands.length; i++) {
            int[] targetArr = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
            Arrays.sort(targetArr);
            answer[i] = targetArr[commands[i][2] - 1];
        }

        return answer;
    }
}

[퀵 정렬 알고리즘을 직접 구현한 버전]

import java.util.*;
public class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for (int i = 0; i < commands.length; i++) {
            int[] targetArr = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
            quickSort(targetArr, 0, targetArr.length - 1);
            answer[i] = targetArr[commands[i][2] - 1];
        }

        return answer;
    }

    private static void quickSort(int[] array, int left, int right) {
        if (left < right) { // left와 right가 같을때 끝나는 조건문, 정복을 담당
            int pivot = partition(array, left, right); // 정렬

            quickSort(array, left, pivot - 1); // pivot 기준 왼쪽 부분 처리
            quickSort(array, pivot + 1, right); // pivot 기준 오른쪽 부분 처리
        }
    }

    private static int partition(int[] array, int left, int right) {
        int pivot = array[right]; // 가장 오른쪽을 기준으로잡고
        int i = (left - 1); // 가장 왼쪽부터 시작

        for (int j = left; j <= right - 1; j++) { // j는 가장 왼쪽 부터 시작 피봇 직전까지 순회
            if (array[j] <= pivot) { // 피봇보다 작으면 i와 j를 스왑
                i++;
                swap(array, i, j);
            }
        }

        swap(array, i + 1, right);
        return (i + 1); // 처리한 영역의 가장 마지막 인덱스 + 1 반환
    }

    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}