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() 을 이용해서 맨 마지막 값은 지워지도록 했다.