알고리즘 - 1208. [S/W 문제해결 기본] Flatten 문제

SW Expert Academy 의 1208번 문제입니다.

벽면에 가장 높이 쌓여진 상자의 한 칸을, 가장 낮게 쌓인 상자 위에 옮기는 ‘덤프’ 작업을 반복합니다.
이렇게 최고점과 최저점의 간격을 줄이는 작업을 평탄화(Flatten)이라고 합니다.

제한된 덤프 횟수 내에서 평탄화를 진행한 뒤 최고점-최저점의 높이차를 구합니다.

• 난이도 : 1~2

문제 조건

• 가로 길이는 100으로 주어진다.

• 상자의 높이는 1 이상 100 이하이다.

• 덤프 횟수는 1 이상 1000 이하이다.

• 주어진 덤프 횟수 이내에 평탄화가 완료(최고-최저 높이 차가 1 이내)되면 그 높이차를 반환한다.

Input

첫 줄에는 테스트 케이스의 덤프 횟수, 다음 줄에는 상자들의 높이가 주어집니다. (총 100열)

Output

테스트 케이스별로 최고점과 최저점의 높이 차를 표시합니다.

생각한 아이디어

최고점, 최저점을 찾는 것이 중요하므로, 입력받은 높이들을 오름차순 정렬해야겠다는 생각을 했습니다.
정렬한 뒤에 최고점은 1을 빼고, 최저점은 1을 더합니다. 그런 다음 다시 오름차순 정렬합니다.
이것을 덤프 횟수만큼 계속 반복하면 끝나는 문제입니다.

저는 C++의 STL 에서 제공하는 Sort 알고리즘을 사용하였습니다.
STL을 사용할 수 있는 환경이라면, 잘 짜여진 라이브러리를 사용하는 것도 좋다고 합니다.

STL의 sort 알고리즘은 algorithm 헤더파일에 존재하며 sort(start, end) 형식으로 사용합니다.
퀵 정렬을 기반으로 구현되어 있고, 기본적으로 오름차순 정렬해 주는 함수입니다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include<iostream>
#include<algorithm>
#define N 100
using namespace std;
int main(int argc, char** argv)
{
	int test_case;
	int T;
	int dump = 0, temp = 0;
	int height = 0;
	int arr[100];
	for (test_case = 1; test_case <= 10; ++test_case)
	{
		cin >> dump;
		for (int i = 0; i < N; i++) {
			cin >> arr[i];
		}
		sort(arr, arr + N);
		for (int k = 0; k < dump; k++) {		            
			arr[N - 1] = arr[N - 1] - 1;
			arr[0] = arr[0] + 1;
			sort(arr, arr + N);   
            
			if (arr[N - 1] - arr[0] <= 1)
				break;
		}
		height = arr[N - 1] - arr[0];
		cout << "#" << test_case << " " << height << endl;
		dump = 0;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

실행 시간이 약 29ms 정도 나왔는데, 10ms 내외로 나오신 분들도 있었습니다.
여기서 무엇을 수정하면 더 줄일 수 있을지 연구해 보면 좋을 것 같습니다.