[프로그래머스] 중앙값 구하기

문제

난이도 : 입문
주어진 숫자배열에서 중앙값을 찾는 문제이다.

문제풀이

• 정렬 후 중앙에 위치한 수를 찾으면된다.

class Solution {
    public int solution(int[] array) {
        int len = array.length;
        for(int i = 0; i<len-1; i++){
            for(int j = i+1; j<len; j++) {
                if (array[i]>array[j]) {
                int pwd = array[i];
                array[i] = array[j];
                array[j] = pwd;
                }
            }
        }
        return array[len/2];
    }
}

• arrays의 sort를 사용한 경우

import java.util.Arrays;

class Solution {
    public int solution(int[] array) {
        Arrays.sort(array);
        return array[array.length/2];
    }
}

정렬을 더 보기

python을 사용할 때는 sort를 통해 자료형에 상관없이 손쉽게 정렬을 하곤 했다.
우선 더 쉽게 하는 방법은 당연히 있을것이다.

함수의 종류:

• java.util.arrays의 sort(int) 함수
• java.util.stream.IntStream의 sorted()함수

arrays에는 parallelSort도 있지만 사용할 일은 없을 것 같다.

자바에서 사용하는 정렬
우선 arrays에서 사용하는 정렬은 DualPivotQuickSort이다.

    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, 0, a.length);
    }

퀵정렬과 듀얼피벗퀵정렬 참고 블로그

DualPivotQuickSort내부에서는 분할, pivot을 정하는 방법이 위 포스트와는 조금 다르다. 예를 들어 포스팅에서는 중앙값 인덱스를 지정한다면, java에서는 (size >> 3) * 3 + 3로 사용한다. 자세한 이해는 시간을 좀더 들여야 할 것 같다.