초보자를 위한 점프대 배치하기

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWGsV8IaAXsDFAVW

오답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/swa_3503/Solution.java

정렬해서 나올 수 있는 모든 경우를 탐색하기 위해 DFS를 하였다. 원형이기 때문에, 시작점을 하나로 DFS 탐색을 시작해도 모든 경우가 커버 가능하다. 예를 들어, 2 4 5 7 9 의 경우에 2를 시작으로 DFS를 탐색한다. 탐색을 하며 높이 차를 계산한다. 시간 초과가 났다. 탐색으로 모든 케이스를 따져보는 것이 아닌 문제라는 것이다.

정답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/swa_3503_02/Solution.java

1. 오름 차순으로 정렬한다.
2. 가장 작은 값을 가운데에 둔다.
3. 맨 앞에, 다음으로 작은 값을 둔다.
4. 맨 뒤에, 다음으로 작은 값을 둔다.
5. 3,4를 반복한다.

이와 같이 하면, 가장 큰 높이 차가 최소가 되도록 정렬된다. 구현을 위해서, 두개의 큐를 사용하였다.

다음 그림을 보자.

1. 주어진 수를 오름 차순 정렬한다.
2. 가장 작은 2를 가운데에 둔다.
3. 그 다음으로 작은 4를 맨 앞에 둔다.
4. 그 다음으로 작은 5를 맨 뒤에 둔다.
5. 3, 4를 반복한다.
6. 최종적으로 7 4 2 5 9 배열이 얻어졌고, 가장 큰 높이 차(4) 가 최소가 되로록 정렬되었다.