[SWEA / Java] 1208번: Flatten (D3)

문제 풀이 날짜: 2023.05.18
포스트 작성일: 2023.05.18

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

Software Expert Academy 1208번 : Flatten (D3) (문제 링크)

 

키워드

완전탐색, 그리디

 

풀이 접근법

• 입력 tc의 개수는 무조건 10개로 고정이다. 입력 배열의 크기도 항상 100으로 고정이다.
• 완전 탐색으로 풀이하였다. 그리디한 발상을 이용하기도 하였다.
• 입력 배열을 정렬하는 것이 핵심이다. 매 순간마다 가장 왼쪽 & 오른쪽 끝 값을 이용하여 덤프 작업을 수행하면 되며, 이렇게 하면 매 반복마다 가장 높이가 높은 곳과 낮은 곳을 일일이 찾을 필요가 없다.
• 가장 왼쪽의 작은 값을 가리키는 lowerBound와 가장 오른쪽의 큰 값을 가리키는 upperBound 계속 찾아주며 덤프 작업을 수행한다. 같은 값이 여러개 있다면 lowerBound는 같은 값들 중 가장 오른쪽 것을 가리키고, upperBound 또한 가장 오른쪽 것을 가리킨다.
  • 풀이 당시에는 가장 작은 값을 가리키는 인덱스, 가장 큰 값을 가리키는 인덱스라는 의미로 lowerBound와 upperBound라는 이름을 썼으나 이분탐색에서 쓰는 개념과 혼동될 여지가 있다. lowerIndex, upperIndex 등으로 바꾸어 쓰는 게 좋을 듯하다.

 

코드

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

public class SWEA1208 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = 10;
		int N = 100;
		
		int[] boxes = new int[N];

		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			int dump = Integer.parseInt(br.readLine());
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int i = 0; i < N; i++) {
				boxes[i] = Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(boxes);
			
			int lowerBound = 0;
			int upperBound = N - 1;
			for(int i = 0; i < dump; i++) {
				//1.dump 작업을 수행한다.
				boxes[lowerBound] += 1;
				boxes[upperBound] -= 1;
				
				//2.다음 lowerBound를 찾는다.
				for(int j = 0; j < N - 1; j++) {
					if(boxes[j] < boxes[j + 1]) {
						lowerBound = j;
						break;
					}
				}
				
				//3.다음 upperBound를 찾는다.
				if(boxes[upperBound] < boxes[upperBound - 1]) {
					upperBound = upperBound - 1;
				}
				else { // upperBound >= upperBound - 1
					upperBound = N - 1;
				}
			}
			
			Arrays.sort(boxes);
			
			int result = boxes[N - 1] - boxes[0];
			sb.append("#" + test_case + " ").append(result).append('\n');
		}
        
        System.out.print(sb);
	}
}

---

lowerBound와 upperBound를 찾는 방식이 조금 깔끔하지 못하다. 입력의 크기가 더 커진다면 이러한 방식은 사용할 수 없을 것이다. 풀이를 마친 후 다른 분들의 풀이를 참고해보니, 덤프 작업을 수행할 때마다 배열을 정렬하는 방법도 있었다. 그 방식을 사용한다면 코드를 더욱 깔끔하게 줄일 수 있을 듯하다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day5/SWEA1208.java