백준 알고리즘 [분할정복] 치킨 TOP N_11582_실버4

문제

인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많아 혼자 정렬을 하기에는 많은 시간이 걸려 C.T.P 회원들을 활용하기로 했다. 치킨집이 N개 있다고 가정을 하자. N개의 치킨의 수치를 무작위로 놓은 뒤 N/2명의 C.T.P 회원이 차례대로 2개의 치킨집을 선택해  정렬을 한다. 그 뒤 N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택 하여 치킨집을 정렬을 한다. 계속해서 N/8명, N/16명이 정렬을 진행하다가 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료한다.
예를 들어 8개의 치킨집의 점수가 (1, 5, 2, 4, 2, 9, 7, 3)과 같을 때, 첫 번째로 4명의 회원이(1, 5), (2, 4), (2, 9), (7, 3)을 각각 정렬하게 되면 (1, 5), (2, 4), (2, 9), (3, 7)이 되고, 두 번째로 2명의 회원이 ((1, 5), (2, 4))와 ((2, 9), (3, 7))을 정렬하면 (1, 2, 4, 5), (2, 3, 7, 9)가 되고, 최종적으로 1명의 회원이 ((1, 2, 4, 5), (2, 3, 7, 9))을 정렬하여 (1, 2, 2, 3, 4, 5, 7, 9)을 만들게 된다.
작업을 진행하던 중 문득 민호는 작업의 중간단계가 궁금해졌다. 현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력해라.

 

체감 난이도

실버 2

 

문제 풀이 소감

부분 배열 정렬하는법 알아 둘 것
배열에서 부분만 정렬하는 방법이 있음!

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 치킨집 맛의 수치를 오름순으로 정렬
 *
 */
public class Main {

    static int N, K;
    static int[] ListA;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        ListA = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            ListA[i] = Integer.parseInt(st.nextToken());
        }
        K = Integer.parseInt(br.readLine());

        // 분할 정복 방식으로 맛 순위 계산
        tasteRank(ListA, N);
    }

    private static void tasteRank(int[] ListA, int size) {
        int subArraySize = 1; // 초기 부분 배열 크기

        while (subArraySize <= size) {
            for (int i = 0; i < size; i += subArraySize) {
                // 부분 배열 정렬
                Arrays.sort(ListA, i, Math.min(i + subArraySize, size));
            }

            // 부분 배열 크기를 기준으로 K단계를 확인
            if (subArraySize == size / K) {
                printArray(ListA);
                return;
            }

            subArraySize *= 2; // 부분 배열 크기 두 배로 증가
        }
    }

    private static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int num : arr) {
            sb.append(num).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

 

문제 바로가기

https://www.acmicpc.net/problem/11582