[백준] 11582번 - 치킨 TOP N

문제

인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 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명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력해라.

입력

• 첫 번째 줄에 치킨집의 개수 N(4 ≤ N ≤ 220)이 주어진다. N은 항상 2의 거듭제곱 꼴이다.
• 두 번째 줄에는 N개의 치킨집의 맛의 수치들이 빈칸을 구분으로 주어지며 이 값은 10억보다 작거나 같은 자연수 또는 0이다.
• 세 번째 줄에는 현재 정렬을 진행중인 회원들의 수 k(1 ≤ k < N)가 주어진다. k 또한 2의 거듭제곱 꼴이다.

출력

• 현재 단계에서 k명이 정렬을 진행한다고 할 때, 현재 단계가 완료한 상태를 출력하라.

예제 결과

코드 구현

1차 시도 코드 - 오직 예제에 나온 경우만 통과 ( k == 2 일 때 )
// ToDo : 이렇게 되는건 k가 2일때의 경우니까 다수의 경우를 생각하기

package 분할정복;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class BJ11582 {

    // 변수 선언
    static int len;            // N
    static int[] chickenRate;  // N개의 치킨집의 맛의 수치 (1 5 2 4 2 9 7 3)
    static int peopleNum;      // k

    public static void main(String[] args) {

        // 치킨집의 개수, N 입력받기
        Scanner sc = new Scanner(System.in);
        len = sc.nextInt();

        // 치킨집 맛의 수치 입력받기
        chickenRate = new int[len];
        for (int i = 0; i < len; i++) {
            chickenRate[i] = sc.nextInt();
        }

        // 정렬을 진행 중인 회원들의 수, k 입력받기
        peopleNum = sc.nextInt();

        int index = len / peopleNum;    // N / k

        ArrayList<Integer> left;
        ArrayList<Integer> right;

				// 각각 정렬 수행
        left = merge_sort(0, index);    
        right = merge_sort(index, len);
        
        left.addAll(right);    // 하나로 합치기
        System.out.println(left);    // 정답 출력

    }

    public static ArrayList<Integer> merge_sort(int start, int end) {
        // 정렬을 위한 ArrayList 선언
        ArrayList<Integer> answer = new ArrayList<Integer>();

        for (int i = start; i < end; i++) {
            answer.add(chickenRate[i]);
        }
        Collections.sort(answer);
        return answer;
    }
}

2차 시도 코드 (정답 출력 부분 수정 후 통과 !)

package 분할정복;

import java.util.*;

public class BJ11582 {
    public static void main(String[] args) {
        // 변수 선언
        int N;      // N
        ArrayList<Integer> chickenRate = new ArrayList<>();  // N개의 치킨집의 맛의 수치 (1 5 2 4 2 9 7 3)
        int k;      // k

        // 치킨집의 개수, N 입력받기
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        // 치킨집 맛의 수치 입력받기
        for (int i = 0; i < N; i++) {
            chickenRate.add(sc.nextInt());
        }

        // 정렬을 진행 중인 회원들의 수, k 입력받기
        k = sc.nextInt();

        int index = N / k;    // N / k

        ArrayList<Integer> sortedRate = new ArrayList<>();

        // k개로 쪼개고 -> 쪼개진거 부분에서 정렬 -> 정답 리스트에 add
        int subIndex = index;
        for (int i = 0; i < N; i+=index) {
            List<Integer> temp = new ArrayList<>(chickenRate.subList(i, subIndex));     // 자르기
            Collections.sort(temp);     // 정렬하고
            sortedRate.addAll(temp);    // 정답 리스트에 쌓기

            // 다음번 subList 인덱스를 위해 계산
            subIndex += index;
        }

        // 정답 출력
        for (int i = 0; i < sortedRate.size(); i++) {
            System.out.printf(String.valueOf(sortedRate.get(i)) + " ");
        }
    }
}

참고 자료

알고리즘 - 분할정복(Divide & Conquer)