11582 치킨 TOP N

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


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());
		Queue <Integer> chicken = new LinkedList<>();
		StringBuilder result = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		
		for(int i=0; i<N; i++) {
			chicken.add(Integer.parseInt(st.nextToken()));
		}
		
		int M =  Integer.parseInt(br.readLine());
		
		for(int k=1; k<=N/(2*M); k*=2) {
		
			int number [] = new int [2*k];
			int size = N/ (2*k);
			
			while(size --> 0) {
				
			for(int i=0; i<2*k; i++) {
				number[i] = chicken.poll();
			}
			
			Arrays.sort(number);
			
			
			for(int i=0; i<2*k; i++) {
				chicken.add(number[i]);
			}
		 }
		}
				
		while(!chicken.isEmpty()) {
			result.append(chicken.poll()).append(" ");
		}
		
		System.out.println(result.toString().trim());
	}
}

 

 

내가 사용한 방법은 다음과 같다.

 

일단 예시로 나온

1 5 2 4 2 9 7 3 을 큐(chicken) 에 넣는다.

 

<1> 4명이 2개의 치킨집을 정렬

 

이때, 맨 처음에는 4명이 각각 2개의 치킨집을 정렬한다고 했다.

즉,

1 5 

2 4 

2 9

7 3

을 각각 정렬하면 된다.

 

그러면

 

1 5 

2 4

2 9

3 7 

이 된다.

 

이렇게 만드는 방법은,

먼저 크기 2의 배열 number 을 만든다.

그리고 1 5 를 배열에 넣고,

배열의 Arrays.sort 메서드를 사용해서

오름차순 정렬한다.

 

그런다음 정렬된 1 5 를 다시 큐(chicken) 에 넣는다.

 

2 4 

2 9

7 3 도 마찬가지이다.

 

그러면 큐에는 

1 5 2 4 2 9 3 7 인 상태가 된다.

 

<2> 2명이 4개의 치킨집을 정렬

 

4크기의 배열(number) 을 만든다.

 

큐에서 1 5 2 4 값을 꺼내서 배열(number) 에 넣고 정렬한 뒤 다시 큐에 넣는다.

 

위와 같은 상황을 반복한다.

 

위에서 설명했듯이, 배열(number) 이 처음에는 2, 그 다음에는 4 크기가 되기 때문에 

아래와 같이 k = 1 2 4 .. 이런 식으로 늘려가면서 배열 크기를 조절했다.

 

		int number [] = new int [2*k];

그리고 이 코드에서 핵심이 되는 코드가 아래 코드인데, 이에 대해 설명하겠다.

 

	for(int k=1; k<=N/(2*M); k*=2) {
		
			int number [] = new int [2*k];
			int size = N/ (2*k);
			
			while(size --> 0) {
				
			for(int i=0; i<2*k; i++) {
				number[i] = chicken.poll();
			}
			
			Arrays.sort(number);
			
			
			for(int i=0; i<2*k; i++) {
				chicken.add(number[i]);
			}
		 }
		}

일단 for 문을 보면 아래와 같은 범위이다.

 

	for(int k=1; k<=N/(2*M); k*=2)

k = 1 일때는 8개의 치킨 점수를 4명의 사람이 2개씩 나눠서 정렬하는 경우이다.

즉, 2 크기의 배열을 만든 뒤, 값을 넣어 정렬하는 과정을 4번 한다.

이를 조절해주는 것이 while 문이다.

			int size = N/ (2*k);
			
			while(size --> 0)

size 값을 정해주고,

while 문이 진행되도록 했다.

이 경우는 총 4번 while 문이 반복된다.

 

k = 2 일때는 8개의 치킨집을 2명이 4개씩 나눠서 정렬하는 경우이다.

그래서 이 경우는 while 문이 총 2번 진행되도록 했다.

 

# for 문 설명

 

	for(int k=1; k<=N/(2*M); k*=2)

1) k 증감식 : k *= 2

k = 1 일때는 8개의 치킨집을 4명이 2개씩 정렬

k = 2 일때는 8개의 치킨집을 2명이 4개씩 정렬한다고 했다.

k = 4 일때는 8개의 치킨집을 1명이 8개 정렬된다.

즉, k 가 2의 배수로 증감이 이뤄진다.

 

2) k 의 범위 : k <= N/(2*M)

 

k = 1 일때는 8개의 치킨집을 4명이 2개씩 정렬한다고 했다.

만약 여기까지만 정렬한 뒤 그 결과를 반환한다면 M = 4(명) 이다.

(여기서 M 은, 문제에서 세번쨰 줄에 제공된 회원들의 수를 받은 값이다.)

 

k = 1 일 때를 지나서,

k = 2 일때도 정렬이 진행된다면, 이 경우는 8개의 치킨집을 2명이 4개씩 정렬하는 경우이고,

여기까지 정렬한 뒤 그 결과를 반환한다면 그 때 M = 2(명) 이다.

 

즉, 위의 k = 1, N= 8(치킨집 수 ), M = 4

k = 2, N = 8, M = 2

이 값들을 계속 만들어 가며 식을 세우면

k<= N/(2*M) 을 만들 수 있다.

 

3) while 문 size 변수 식 : size = N/(2*k)

 

k = 1 일때, while 문을 4번 돌린다고 했다.

k = 2 일때, while 문을 2번 돌린다.

이렇게 값을 만들면서 보면,

 

그 횟수인 size = N/(2*k) 를 만들 수 있다.

 

# 덧붙이는 설명

 

값을 출력할 떄, StringBuilder 를 이용했다.

큐(chicken) 에서 값을 꺼내 StringBuilder 에 붙이고, 공백을 붙여주는 것을 반복했는데,

그러다 보니 맨 마지막에도 공백이 붙여진다.

 

그런데 맨 마지막 공백은 없어야 하므로,

trim() 을 이용해서 맨 마지막 값은 지워지도록 했다.