728x90
처음에는 ArrayList를 매번 정렬하는 방법으로 풀었는데, 우선순위 큐를 이용하면 더 쉽게 풀릴 것 같아서 두 가지 방법을 모두 써봤다.
- ArrayList
int N = sc.nextInt(); // 덤프 횟수
ArrayList<Integer> box = new ArrayList<>();
for (int i = 0; i < size; i++) {
box.add(sc.nextInt());
}
Collections.sort(box);
int dis = box.get(size - 1) - box.get(0);
while (N > 0 && dis > 1) {
box.set(0, box.get(0) + 1);
box.set(size - 1, box.get(size - 1) - 1);
Collections.sort(box);
dis = box.get(size - 1) - box.get(0);
N--;
}
N(덤프 횟수)가 0보다 크고, dis(가장 큰 원소와 작은 원소의 차이)가 1보다 큰 경우에만 while문이 실행된다
정렬을 루프 한 번마다 반복하므로, 0번 원소가 가장 작고 1번 원소가 가장 크다. 각 값을 수정해주고, 다시 dis를 업데이트한 후 N을 1씩 감소시키며 과정을 진행한다
거리가 1이나 0이 되거나, 덤프 횟수가 소진되었을 때가 종료조건이다.
전체 코드
package SWEA0809;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class SWEA_1208_Flattern {
public static void main(String[] args) {
int T = 10;
int size = 100;
Scanner sc = new Scanner(System.in);
for (int t = 0; t < T; t++) {
int N = sc.nextInt(); // 덤프 횟수
ArrayList<Integer> box = new ArrayList<>();
for (int i = 0; i < size; i++) {
box.add(sc.nextInt());
}
Collections.sort(box);
int dis = box.get(size - 1) - box.get(0);
while (N > 0 && dis > 1) {
box.set(0, box.get(0) + 1);
box.set(size - 1, box.get(size - 1) - 1);
Collections.sort(box);
dis = box.get(size - 1) - box.get(0);
N--;
}
System.out.println("#" + (t + 1) + " " + dis);
}
}
}
2. 우선순위 큐 (Heap)
우선순위 큐는 우선순위가 낮은 원소를 poll하기 때문에 maxHeap과 minHeap을 구현하였다.
maxHeap에서 poll을 할 경우 가장 작은 원소가 반환되고, minHeap에서 poll할 경우 가장 큰 원소가 반환된다.
dis를 구할 때 각각의 heap에서 poll을 한 후, max에서 1을 빼고 min에서 1을 더한 값을 각각의 box에 다시 넣어준다.
PriorityQueue<Integer> maxbox = new PriorityQueue<>();
PriorityQueue<Integer> minbox = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < size; i++) {
int n = sc.nextInt();
maxbox.offer(n);
minbox.offer(n);
}
int dis = minbox.peek() - maxbox.peek();
while (N > 0 && dis > 1) {
int min = maxbox.poll();
int max = minbox.poll();
minbox.offer(max - 1);
maxbox.offer(min + 1);
dis = minbox.peek() - maxbox.peek();
N--;
}
전체 코드
package SWEA0809;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
public class SWEA_1208_Flattern_heap {
public static void main(String[] args) {
int T = 10;
int size = 100;
Scanner sc = new Scanner(System.in);
for (int t = 0; t < T; t++) {
int N = sc.nextInt(); // 덤프 횟수
PriorityQueue<Integer> maxbox = new PriorityQueue<>();
PriorityQueue<Integer> minbox = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < size; i++) {
int n = sc.nextInt();
maxbox.offer(n);
minbox.offer(n);
}
int dis = minbox.peek() - maxbox.peek();
while (N > 0 && dis > 1) {
int min = maxbox.poll();
int max = minbox.poll();
minbox.offer(max - 1);
maxbox.offer(min + 1);
dis = minbox.peek() - maxbox.peek();
N--;
}
System.out.println("#" + (t + 1) + " " + dis);
}
}
}
728x90
'문제 풀이 > SWEA' 카테고리의 다른 글
[SWEA] 6190 - 정곤이의 단조 증가하는 수 (자바/Java) (0) | 2022.08.11 |
---|---|
[SWEA] 1954 - 달팽이 숫자 (자바/Java) (0) | 2022.08.10 |
[SWEA] 4789 - 성공적인 공연 기획 (자바 / Java) (0) | 2022.08.09 |
[SWEA] 1220 - Magnetic (자바/Java) (0) | 2022.07.29 |
[SWEA] 12712 - 파리퇴치 3 (자바/Java) (0) | 2022.07.29 |