[SWEA] 14510. 나무 높이 - Java

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AYFofW8qpXYDFAR4 

SW Expert Academy

---

1. 문제 요약

N개의 나무가 있고 모든 나무의 키가 처음 가장 키 큰 나무와 같아지도록 하는 최소 일자를 구하는 문제이다.

홀수 일은 1만큼, 짝수 일은 2만큼 자라며 하루에 자라지 않을 수도 있다.

 

2. 풀이

그리디 문제이다.

입력받을 때 가장 높은 나무 키를 Math.max로 갱신하면서 구해준다.

 

처음에는 max와 각각 나무와의 차이를 모두 더해서 짝수 큐 안에 들어갈 수있는 만큼 2를 넣어주고 홀수면 홀수 큐에 1을 하나 넣어주고 시작했다. 이러면 짝수큐에는 2 여러 개, 홀수 큐에는 1 하나가 들어간다.

짝수 큐 안에 들어있는 2를 poll 하고 홀수 큐에 1을 두 번 offer 해줌을 반복하면서

홀수 큐 사이즈가 짝수 큐 사이즈보다 크거나 같아지면 반복을 멈춘다.

홀수 큐 사이즈는 홀수 일, 짝수 큐 사이즈는 짝수 일을 의미한다.

그래서 (짝수 큐의 사이즈 + 홀수 큐의 사이즈)를 답으로 구했다.

 

근데 이렇게 하면 여러 개의 나무가 높이 1씩 남았을 때, 짝수일은 2가 더해지므로 짝수 일자는 쉬어야 하는데

이 조건을 고려하지 않았다. 그래서 차이를 전부 더하고 시작하는 방법은 잘못되었다.

 

그래서 바꾼 방법은, for문으로 나무 하나씩 볼 때 키가 짝수면 짝수 큐에 들어갈 수 있는 만큼 2를 넣어주고 홀수면 홀수 큐에 1을 넣어줬다. 이렇게 하면 짝수 큐에 2 여러 개, 홀수 큐에 1 여러 개가 들어간다.

마찬가지로 

짝수 큐 안에 들어있는 2를 poll 하고 홀수 큐에 1을 두 번 offer 해줌을 반복하면서

홀수 큐 사이즈가 짝수 큐 사이즈보다 크거나 같아지면 반복을 멈춘다.

 

추가한 조건은, 처음부터 홀수 큐 사이즈가 짝수 큐 사이즈보다 클 때,

((짝수 큐 사이즈 * 2) + (남은 홀수 큐 사이즈 + 남은 홀수 큐 사이즈 -1)) 을 답으로 구했다.

남은 홀수 큐 사이즈는 홀수 일,

남은 홀수 큐 사이즈-1은 쉬어가는 짝수 일을 의미한다.

 

문제 풀이 방법은 깜찍girl의 도움을 받았다.

 

3. 코드

package a22_10_25;

import java.util.*;
import java.io.*;

public class SW_14510_나무높이 {

	static Queue<Integer> even_q, odd_q;
	static int N, ans, max;
	static int[] tree;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			tree = new int[N];
			max = 0;
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				tree[i] = Integer.parseInt(st.nextToken());
				max = Math.max(max, tree[i]);
			} // 입력 끝

			ans = 0;
			solution();
			System.out.println("#" + tc + " " + ans);
		}
	}

	static void solution() {
		even_q = new ArrayDeque<>();
		odd_q = new ArrayDeque<>();

		for (int num = 0; num < N; num++) {
			if (tree[num] == max) continue;

			int n = max - tree[num];
			// 초기화
			for (int i = 0; i < n / 2; i++) {
				even_q.offer(2);
			}
			if (n % 2 != 0) odd_q.offer(1);
		}

		// 계산
		if (even_q.size() >= odd_q.size()) {
			while (true) {
				if (even_q.size() <= odd_q.size()) {
					ans = even_q.size() + odd_q.size();
					break;
				}
				even_q.poll();
				odd_q.offer(1);
				odd_q.offer(1);
			}
		} else if (even_q.size() < odd_q.size()) {
			ans += even_q.size() * 2;
			int gap = odd_q.size() - even_q.size();
			ans += gap + (gap - 1);
		}
	}
}