[코드트리 챌린지] 중앙값 계산2

코드트리 3주 차 블로그챌린지입니다.

저는 기업별 커리큘럼을 신청하였고 오늘은 삼성 커리큘럼을 풀어 보았습니다

중앙값 계산 2 문제를 리뷰해보고자 합니다

https://www.codetree.ai/cote/13/problems/get-median-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---

풀이방법

• 순서대로 숫자를 읽다가 홀수번째에 중앙값을 찾아 출력
• 현재 시점에 중앙값을 찾아야하기 때문에 필요한 시점에 정렬을 한 후 중앙값을 읽는다
• 매 번 정렬을 해야하는 비용이 신경쓰여서 한 번에 처리하는 방법을 고민해봤지만 특정 시점을 기준으로 중앙값을 찾아야하므로 매 번 정렬을 해야 함

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if(i % 2 == 0) {
                Arrays.sort(arr, 0, i+1);
                sb.append(arr[i/2]).append(" ");
            }
        }
        System.out.println(sb);
        br.close();
    }
}