[SWEA] 1208 Flatten

코드

import java.util.Scanner;
//
public class Solution_1208_ {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = 10;
		
		for(int t =1 ; t <= tc; t++ ) {
			int[] arr= new int[100];
			int ans = -1;
			int maxH = Integer.MIN_VALUE;
			int minH = Integer.MAX_VALUE;
			int maxIdx = -1;
			int minIdx = -1;
			int dump = sc.nextInt();
			
			
			for(int i = 0; i < arr.length; i++) {
				arr[i] = sc.nextInt();
				if(maxH < arr[i]) {
					maxH = arr[i];		
					maxIdx = i;
					
				}
				if(minH > arr[i]) {
					minH = arr[i];
					minIdx = i;
				}
			}
			for(int k = 0; k < dump; k++) {
				arr[maxIdx]--;
				arr[minIdx]++;
				maxH--;
				minH++;
				for(int i = 0; i < arr.length; i++) {
					if(maxH < arr[i]) {
						maxH = arr[i];
						maxIdx = i;
						
					}
					if(minH > arr[i]) {
						minH = arr[i];
						minIdx = i;
					}
				}
				ans = maxH - minH;
				if(ans == 0 || ans == 1) {
					break;
				}
			}
			System.out.println("#" + t + " " + ans);
		}
	}
}

다른 참고 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 * 접근 방식
 * - 박스의 높이가 1~100인 걸 활용해 높이에 해당하는 갯수를 저장한 배열
 * - 입력을 받을 때 상자의 높이의 개수를 count해주고  최대, 최소값을 갱신해준다.
 * 
 * 1. min개의 개수를 가진 인덱스를 찾아가 -1하고 min+1개의 개수를 가진 인덱스에서 +1
 *  
 *  
 * 2. max개의 개수를 가진 인덱스를 찾아가 -1하고 max+1개의 개수를 가진 인덱스에서 +1
 * 
 * 
 * 3. 높이[min], 높이[max]가 0이면, 0이 아닌 다음 min과 max를 찾아서 갱신해준다.
 * 
 * 
 * dump 수만큼 1~3 과정 반복
 */
public class Solution_1208_xxx_2 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for(int t=1;t<=10;t++) {
			int N = Integer.parseInt(br.readLine()); // 덤프 횟수
			int[] box = new int[101]; 
			StringTokenizer st = new StringTokenizer(br.readLine());
			int min = Integer.MAX_VALUE;
			int max = -1; 
			for(int i=0;i<100;i++) {
				int hight = Integer.parseInt(st.nextToken()); // 
				box[hight]++; //높이를 인덱스로하고 같은 높이의 원소를 카운트한것을 값으로함. 
				max = Math.max(max, hight); //높이에 대한 max임
				min = Math.min(min, hight); //높이에 대한 min
			}
			
//			과정 1~2
			for(int i=0;i<N;i++) {
//				최소값은 1개 줄여주고 최소값보다 +1인 갯수는 1개 증가
				box[min] -= 1; //min에 해당하는 갯수를 하나 줄임
				box[min+1] += 1; //min+1에 해당하는 개수를 하나 늘림.???? 아 
				//최대 높이 블록를 하나 옮기면 min 높이 블록은 하나 없어지고 m+1 높이 블록은 하나 추가되겠네   
				
//				최대값은 1개 줄여주고 최대값-1인 것의 개수는 1개 증가
				box[max] -= 1; //최대값에 해당하는 갯수를 하나 줄임
				box[max-1] += 1; //max-1 높이에 해당하는 갯수를 하나 늘림....??? 아하 
				
				
//				과정 3
				while(box[min] == 0) { //현재 min높이에 해당하는 블록 갯수가 0이 된거니까 min+1 높이로 기준으로 바꿔준다. 
					min++;
				}
				while(box[max] == 0) {
					max--;
				}
				if(max == min) {
					break;
				}
			}
			System.out.printf("#%d %d\n",t,(max-min));
		}
	}
}

참고 코드 풀이

여기선 높이 자체를 배열 인덱스로 설정했고 배열의 값은 곧 인덱스 높이에 있는 블록의 개수를 의미한다. MIN높이 혹은 MAX높이를 가지고 있는 블록이 1개 이상일 수 있기 때문이다.

⭐ 덤프가 반복 될 때마다 MIN 높이 블록의 개수를 하나씩 줄여가고 그것은 곧 MIN+1 높이의 블록의 개수가 하나씩 늘어난다는 것이다.
결국 개수가 0이 됐을 때, while (MIN 높이++) 반복을 통해서 다음으로 MIN 높이를 가지고 있는 1개 이상의 블록을 찾는다.

🔥❓ 근데 어차피 MIN높이에서 딱 한 높이만 올라갈 수 있기 때문에 즉, MIN높이의 개수가 0이 된다는 뜻은 모든 MIN높이였던 블록이 MIN+1높이가 됐다는 것을 의미하기 때문에 굳이 WHILE문을 돌리지 않고 MIN++를 해도 될 것같음..!