Note: 해당 알고리즘은 java로 풀이되었습니다.

문제 보기

문제 분석

Flatten 문제는 D3치고는 쉬운 난이도에 속합니다.
sort만 알면 굉장히 쉽게 풀 수 있었는데요.
sort를 몰랐던 분들이라면 알고리즘에 굉장히 많이 쓰이니, 이번 기회에 반드시 알아주시기 바랍니다.

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("res/Flatten.txt"));
		Scanner sc = new Scanner(System.in);
		for (int t = 1; t <= 10; t++) {
			int dump = sc.nextInt();
			int[] box = new int[100];
			for (int i = 0; i < 100; i++) {
				box[i] = sc.nextInt();
			}
			Arrays.sort(a);
			for (int i = 0; i < dump; i++) {
				if (--box[99] - ++box[0] < 2)
					break;
				Arrays.sort(box);
			}
			System.out.println("#" + t + " " + (box[99] - box[0]));
		}
		sc.close();
	}

일단 9번 라인까지는 입력을 받는 부분이기 때문에 10번 라인 부터 설명하겠습니다. 참고로 이번 알고리즘은 Array를 쓰지않고 배열을 사용했는데 Array를 사용하셔도 전혀 상관 없습니다.

Arrays.sort(a);
	for (int i = 0; i < dump; i++) {
		if (--box[99] - ++box[0] < 2)
			break;
		Arrays.sort(a);
}

먼저 전체 배열을 sort를 해줍니다.
그러면 배열의 값이 가장 낮은 값 부터 가장 높은 값까지 오름차순으로 정렬됩니다.
그 다음에 가장 높은 값에서 1을 빼고 가장 낮은 값에 1을 더하면 되겠지요.
가장 높은 값은 배열의 마지막 값인 box[99]에, 가장 낮은 값은 box[0]에 저장 되엇겠죠.
가감을 한 뒤에는 값에 변화가 생겼기 때문에 다시 한 번 sort를 해줘야 합니다.
그리고 이것은 반복문을 돌려 입력받은 값만큼 반복하면 되겠습니다.

반복문을 빠져나가는 조건이 있습니다.
가장 큰 값과 가장 작은 값이 0또는 1이 나올 때입니다.
이때는 break를 하게 했습니다.
저는 겉멋 부린다고

if (--box[99] - ++box[0] < 2)
			break;

이런식으로 풀었는데 꼭 이렇게 안하고 풀어 쓰셔도 됩니다.(사실 풀어 쓰는 것을 더 추천합니다. 알고리즘 문제 중에 코드 길이를 검사하는 경우는 없으니)
굳이 설명 드리자면 전위 연산자로 가장 큰값에 1을 빼고 가장 작은 값에 1을 더한 것입니다.

System.out.println("#" + t + " " + (box[99] - box[0]));

마지막으로 가장 큰값과 가장 작은 값의 차를 출력하면 됩니다.

후기

sort만 안다면 크게 어렵지 않은 문제였습니다.
sort를 계속 반복해서 돌리는 것에 거부감을 느끼시는 사람이 있을 수 있습니다.
만약에 값이 엄청나게 많다거나 시간이 엄청나게 부족하다면 다른 풀이방법으로 최대한 시간복잡도를 줄일 수 도 있습니다.
하지만 이 문제는 배열의 값이 100개로 고정, 반복도 1000번 이하로 한다는 점, 제한 시간이 20초로 넉넉하다는 점으로 시간 복잡도에 대해 신경을 쓰지 않아도 되는 문제였습니다.
시간 복잡도와 공간복잡도에 관한 포스트는 기회가 되면 다음에 하도록 하겠습니다.

만약 코드를 다운 받고 싶다면 공유한 깃허브에 접속해주세요.
오류 지적, 질문, 더 나은 풀이는 언제든지 메일이나 댓글로 부탁드립니다.
감사합니다.