1208번 - Flatten

문제의 저작권은 SW Expert Academy에 있습니다. (출처)

1. 문제
   1-1. 문제 설명
   1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

1. 문제

1-1. 문제 설명

 

1-2. 문제 해석

블록을 움직여서 최고점과 최저점의 차이를 최소로 줄였을 때, 그 차이를 출력하는 문제이다.

만약 블록을 움직이는 횟수에 제한이 없다면 아주 쉬운 문제가 됐을 것이다. 차이가 0 아니면 1이 나왔을 테니까.

하지만 이 문제는 이동 횟수가 정해져 있다.

 

문제에서 요구하는 동작은 기본적으로 다음과 같다.

"가장 높은 곳에서 블록을 가져와 가장 낮은 곳으로 옮겨라"

가장 높은 곳을 찾아서 -1을 하고 가장 낮은 곳을 찾아서 +1을 하면 된다는 뜻이다.

이를 이동 횟수만큼 반복하면 된다.

 

처음에는 포문을 돌면서 최댓값 최솟값을 찾을까 생각했었다.

근데 어차피 일일이 다 돌면서 비교 검사할 거면...

정렬을 하고 첫 번째 값과 마지막 값을 이용하면 간단하지 않을까 라는 생각이 들었다.

맨 처음만 정렬하고 나면 이후에는 거의 정렬된 배열을 가지고 다시 정렬하는 거니까 효율 측면에서 손해가 많이 없을 것이라 생각했다.

 

 

2. 코드

public class Day1_1208_Flatten {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = 10;

		for (int i = 0; i < T; i++) {
			int moves = Integer.valueOf(br.readLine());
			String[] input = br.readLine().split(" ");
			int[] arr = new int[input.length];
			for (int j = 0; j < input.length; j++) {
				arr[j] = Integer.valueOf(input[j]);
			}

			while (moves-- > 0) {
				Arrays.sort(arr);
				arr[0]++;
				arr[arr.length - 1]--;
			}

			Arrays.sort(arr);
			sb.append("#").append(i + 1).append(" ").append(arr[arr.length - 1] - arr[0]).append("\n");
		}

		System.out.println(sb.toString());
	}
}

실행 시간 단축하고자 사용한 StringBuilder에 append 하는 부분이 좀 더럽긴 하다.

(나중에 테스트해봤는데 그냥 sb.append("#" + (i + 1) + " " + ... ) 이런 식으로 사용해도 속도 차이가 크게 안 난다)

 

 

3. 실행시간

항상 순위권을 먹는 우**님, 이**님... 나는 3등...

 

125ms로 반에서 3등을 했다.

대체 2배나 긴 코드로 어떻게 저렇게 짧은 실행시간이 나왔는지 궁금하지만

내 자존심과 포인트가(열람하면 포인트 차감됨) 허락하지 않는다.

 

 

 

 

 

---

💡 느낀 점

• C++은 진짜 진짜 빠른 것 같다.
• 이번 문제는 정렬을 사용하는 게 코드가 더 간결해지는 듯하다.

---