코딩 문제 - 중앙값 구하기

중앙값 구하기
문제 설명
중앙값은 어떤 주어진 값들을 크기의 순서대로 정렬했을 때 가장 중앙에 위치하는 값을 의미합니다. 예를 들어 1, 2, 7, 10, 11의 중앙값은 7입니다. 정수 배열 array가 매개변수로 주어질 때, 중앙값을 return 하도록 solution 함수를 완성해보세요.

제한사항
array의 길이는 홀수입니다.
0 < array의 길이 < 100
-1,000 < array의 원소 < 1,000
입출력 예
array result
[1, 2, 7, 10, 11] 7
[9, -1, 0] 0
입출력 예 설명
입출력 예 #1

본문과 동일합니다.
입출력 예 #2

9, -1, 0을 오름차순 정렬하면 -1, 0, 9이고 가장 중앙에 위치하는 값은 0입니다.

 

	public static int solution(int[] numbers) {
		int answer = 0;
		
//		순서대로 배열
//		n+1/2
		quickSort(numbers, 0, numbers.length - 1);
		System.out.println(Arrays.toString(numbers));
		answer =  numbers[numbers.length / 2];
		
		return answer;
	}
	
	public static void quickSort(int[] array, int start, int end) {
		int partNum = partition(array, start, end);
		if(start < partNum - 1) {
			quickSort(array, start, partNum - 1);
		}
		if(partNum < end) {
			quickSort(array, partNum, end);
		}
	}
	
	public static int partition(int[] array, int start, int end) {
		int pivot = array[(start + end) / 2];
		while(start <= end) {
			while(array[start] < pivot) {
				start++;
			}
			while(array[end] > pivot) {
				end--;
			}
			if(start <= end) {
				swap(array, start, end);
				start++;
				end--;
			}	
		}
		return start;
	}
	
	public static void swap(int[] array, int start, int end) {
		int temp = array[start];
		array[start] = array[end];
		array[end] = temp;
	}

 

중앙값 공식

- 전체 자료 개수가 홀수일 때 n + 1 / 2 째 값

- 전체 자료 개수가 짝수일 때 n / 2, (n/2 + 1) 째 값들의 평균 값

 

중앙값 공식은 자바 배열 특성상 인덱스가 0부터 시작한다는걸 고려해서 +1은 제외하고 계산

 

정렬은 자바의 배열함수를 사용해도 되나, 이번 기회에 퀵 정렬을 사용함.

Arrays.sort(array);

퀵 정렬을 이해하기 쉽게 설명한 유튜브 링크

https://youtu.be/7BDzle2n47c