[Coding Test : Java] Lv.0 : 중앙값

문제 상황은 다음과 같다.^[각주:1]

---

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

---

 중요한 점은 array를 sorting하는 것이다. Java에는 util package 아래에 Arrays 라는 친구가 있어서, sort( ) method를 활용하면 쉽게 sorting이 가능하다. 하지만 그렇게 하면 재미가 없다.

 

코딩

import java.util.*;

class Solution {
    public int solution(int[] array) {
        int answer = 0;
        
        Arrays.sort(array);
        
        int index = (array.length - 1) / 2;
        answer = array[index];
        
        return answer;
    }
}

 위 코드는 java 의 util package에 있는 Arrays의 sort( ) method를 활용한 것이다. 아주 단순하다.

 

class Solution {
    public int solution(int[] array) {
        int answer = 0; 
        
        for(int j=array.length-1; j>0; j--){
            for(int i=array.length-1; i>0 ;i--){
                int prev = array[i-1];
                int next = array[i];

                if(prev > next){
                    array[i-1] = next;
                    array[i] = prev;
                } else {
                    continue;
                }
            }
        }
        
        int index = (array.length - 1) / 2;
        answer = array[index];
        
        return answer;
    }
}

 하지만 sorting 을 활용할 수 없다면 어떻게 해야할까? Array에서 하나의 값을 집어 원하는 위치로 가져다놓는다고 생각해보자. Array의 끝에 있는 친구과 그 옆에 있는 친구를 비교해서 크기가 작다면 서로의 위치를 바꿔주는 과정을 array 전체에 걸쳐 진행하도록 한다.

 

10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 1 2
10 9 8 7 6 5 4 1 3 2
        ...

1 10 9 8 7 6 5 4 3 2

 예를 들어 10부터 1까지 역순으로 나열되어 있을 때, 1이라는 친구의 값을 계속해서 비교하여 자리를 바꿔주는 과정을 거치면 1은 가장 처음 오게되고, 나머지가 10부터 2까지 역순으로 나열된 array가 될 것이다. 이것이 array의 하나의 index에 대해 수행한 것이므로, 이를 array 전체로 확장시켜서 반복해준다면 원하는대로 sorting 될 것이다. 그렇게 해서 작성된 것이 위 코드이다.

 

Footnote

1. 코딩테스트 연습 - 중앙값 구하기 | 프로그래머스 스쿨 (programmers.co.kr) [본문으로]