백준 11582번 치킨 TOP N JAVA

링크텍스트

설명

풀이 흐름 설명

문제를 보고 바로 병합정렬 구조라는 것을 파악하였다.
배열을 k명이 나눠서 정렬한다고 가정하면 각 회원이 처리하는 그룹의 크기는 N/k가 된다.
배열 전체 길이 N을 k명으로 나누었으므로 각 회원이 담당하는 구간 길이는 N/k가 되는 것이다.

재귀적으로 배열을 나누면서 현재 구간의 크기가 N/k 이하가 되면 해당 구간만 정렬하도록 구현하였다. 이때 Java의 Arrays.sort를 사용하면 Arrays.sort(arr, left, right+1)처럼 두 번째와 세 번째 인자를 이용해 부분 배열만 정렬할 수 있다.
right + 1을 해야 하는 이유는 Java에서 toIndex는 포함되지 않기 때문이다.

왜 arr.length / k인가?

k명 회원이 현재 단계에서 정렬을 수행한다고 가정하면 전체 배열을 k개의 그룹으로 나눠야 한다.
따라서 각 그룹의 크기 = 전체 배열 길이 N / k
재귀적으로 내려가면서 구간의 크기가 N/k 이하가 되면 더 이상 나누지 않고 그 구간만 정렬한다.
이렇게 해야 현재 단계에서 k명이 정렬한 결과를 정확히 시뮬레이션할 수 있다.

재귀 호출과 구간 처리

재귀 호출 시 왼쪽 구간은 left ~ mid 오른쪽 구간은 mid+1 ~ right로 나누어 호출하였다.
각 그룹의 경계가 올바르게 유지되어 중간 단계에서 k명이 정렬한 상태를 정확히 시뮬레이션할 수 있다.

int mid = (left + right) / 2;
mergeSort(arr, left, mid, k);
mergeSort(arr, mid+1, right, k);

현재 구간 크기 확인

if(right - left + 1 <= arr.length / k)
Arrays.sort(arr, left, right + 1);
구간 크기가 N/k 이하라면 더 이상 재귀를 내려가지 않고 해당 구간만 정렬

Arrays.sort(arr, fromIndex, toIndex)
fromIndex → 포함(inclusive)
toIndex → 미포함(exclusive)
fromIndex부터 toIndex - 1까지 정렬

예시
arr = {1, 5, 2, 4, 3, 6}
groupSize = 3

i = 0 → Arrays.sort(arr, 0, 3) // 0,1,2 정렬
i = 3 → Arrays.sort(arr, 3, 6) // 3,4,5 정렬

버전	범위 지정	+1 필요 여부	이유
반복문 그룹	i ~ i+groupSize-1	없음	toIndex가 미포함이라 i+groupSize까지 지정하면 딱 맞음
재귀	left ~ right	필요	right가 포함되어야 하므로 Arrays.sort(arr, left, right+1)

시간복잡도: O(NlogN), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

// 병합 정렬을 사용한 매개 변수 탐색 문제
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];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int k = Integer.parseInt(br.readLine());

        mergeSort(n, k, arr, 0, n-1);

        StringBuilder sb = new StringBuilder();
        for(int num : arr){
            sb.append(num).append(" ");
        }

        System.out.print(sb);
   }


   public static void mergeSort(int n, int k, int [] arr, int left , int right){
    //if(right - left + 1 <= arr.length / k)
    if(n<=arr.length/k){
        Arrays.sort(arr,left,right+1);
        return;
    }

    int mid = (left+right)/2;
    mergeSort(n/2, k, arr, left, mid);
    mergeSort(n/2, k, arr, mid+1, right);

   }
}

다른 코드

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

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];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int k = Integer.parseInt(br.readLine());

        int groupSize = n / k; // 각 회원이 정렬할 그룹의 크기

        for(int i = 0; i < n; i += groupSize){
            Arrays.sort(arr, i, i + groupSize); // 그룹 단위 정렬
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

https://hongjw1938.tistory.com/193