[SW Expert Academy] 나무 높이 # 14510

나무 높이
이 문제 때문에 몇 날 며칠을 고민했는데...
결국 오늘 풀었다.

10월 14일 쯤에 실패하고, 매일 매일 어떻게 풀지 생각만 하다가 오늘 마침 시간이 나서 풀게 되었다. 결과는 한번에 성공!

오랫동안 매달렸던 문제를 푸니 마음이 한결 가볍다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Solution_14510 {
	static int N; // 나무의 개수
	static int[] map; // 나무 높이의 정보를 저장할 배열
	static int max; // 배열에서 나무의 최대 높이
	static int ans; // 정답 (나무 높이가 모두 같기 위한 최소 날짜)

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 테스트 케이스 수
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
        	// 전역 변수 초기화
        	// 나무의 개수
			N = Integer.parseInt(br.readLine());
            // 나무 정보 저장할 배열
			map = new int[N];
            // 배열에서 나무의 최대 높이
			max = 0;
            // 정답 (나무 높이가 모두 같기 위한 최소 날짜)
			ans = 0;
            
            // 입력
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				map[i] = Integer.parseInt(st.nextToken());
                // 입력 받으면서 전체에서 나무의 최대 높이 찾기
				max = Math.max(max, map[i]);
			}
			solve();

			System.out.println("#" + (t + 1) + " " + ans);
		}
	}

	private static void solve() {
    	// 물을 줘야 할 나무를 저장할 리스트 선언
		List<Integer> tree = new ArrayList<>();
		for (int i = 0; i < map.length; i++) {
			if (map[i] < max) {
            	// 나무의 최대 높이보다 작으면(최대 높이와 다르면) 물을 줘야 함
				tree.add(map[i]);
			}
		}
        
        // 배열의 모든 나무가 최대 높이와 같으면 물을 줄 필요가 없음
		if(tree.size() == 0) {
			return;
		}
        
        // 물을 줘야할 나무들을 역순으로 정렬
		Collections.sort(tree, Collections.reverseOrder());

		// 1일부터 물을 주기 시작
		water(tree, 1);
	}

	private static void water(List<Integer> tree, int day) {
		// 홀수 날
		if (day % 2 == 1) {
        	// 물을 줘야할 나무가 하나가 아니라면 그냥 물 주기
			if (tree.size() != 1) {
				tree.set(0, tree.get(0) + 1);
			}
			// 물 줄게 하나만 남았을 때
			else if (tree.size() == 1) {
				// 딱 2 차이 아닐 때 물 주기
				if (tree.get(0) != max - 2) {
					tree.set(0, tree.get(0) + 1);
				}
				// 딱 2 차이 날 땐 물 안 주기
			}
		}

		// 짝수 날
		else if (day % 2 == 0) {
			if (tree.size() == 1) {
				// 물 줄게 하나 남았는데 2 이상 차이 날 때 물 주기
				if (tree.get(0) != max - 1) {
					tree.set(0, tree.get(0) + 2);
				}
				// 물 줄게 하나 남았는데 1 차이 날 때 다음날 물 주기
			}

			else if (tree.size() != 1) {
				// 물 줄게 하나가 아닌데 처음꺼가 1 차이 나면 다음꺼 주기
				if (tree.get(0) == max - 1) {
					for (int i = 0; i < tree.size(); i++) {
                    	// max와 1 차이 나지 않는 최소 인덱스 구해서
						if(tree.get(i) < max - 1) {
                        	// 물 주고 끝내기
							tree.set(i, tree.get(i) + 2);
							break;
						}
					}
				}
				// 물 줄게 하나가 아니고 처음꺼가 2 이상 차이 나면 물 주기
				else {
					tree.set(0, tree.get(0) + 2);
				}
			}
		}

		Collections.sort(tree, Collections.reverseOrder());

		for (int i = 0; i < tree.size(); i++) {
			if (tree.get(i) == max) {
				tree.remove(i);

				// 더 이상 물을 줄 나무가 없다면 물 주기(water) 종료
				if (tree.size() == 0) {
                	// 정답을 오늘 날짜로 만들어주기
					ans = day;
					return;
				}
			}
			if (tree.get(i) < max) {
				break;
			}
		}

		// 다음 날로 가서 물 주기
		water(tree, day + 1);
	}

}