BOJ#13415 정렬 게임

BOJ#13415 정렬 게임

* 문제

https://www.acmicpc.net/problem/13415

* 풀이

시간 제한 때문에 생각할게 많은 문제입니다.

주어진 정렬 Order를 모두 수행하는 경우 시간 초과가 발생하기 때문입니다.

알고리즘 #1. 필요 없는 정렬 Order는 무시한다.

ex)

10

4 1 5 2 3 10 8 11 15 6

6

3 2

4 5

5 4

3 2

2 1

3 1

오름차순을 (+), 내림차순을 (-)라고 했을 때,

+3 → -2 → +4 → -5 → +5 → -4 → +3 → -2 → +2 → -1 → +3 → -1 에서

+3 → -2 → +4 → -5 → +5 → -4 → +3 → -2 → +2 → -1 → +3 → -1 회색 음영은 수행하지 않아도 되므로

결국 +5 → -4 → +3 → -1 으로 줄일 수 있습니다.

(위 예에서 -5를 +5로 대체해야 함을 주의)

위 과정을 수행하기 위해서는 Stack과 같은 자료 구조가 필요합니다.

삽입하려는 정렬 Order의 절대값과 Stack에 기록된 정렬 Order의 절대값을 비교하여

적절한 Pop, Push를 하면 되겠습니다.

그러나, 정렬 Order를 확정한 뒤

실제 정렬 명령을 수행할 때에는 기록한 순서대로 정렬을 진행해야 하므로(FIFO)

양방향 출입이 가능한 Deque를 이용합시다.

알고리즘 #2. 정렬 시간 단축

위와 같이 필요 없는 정렬 Order를 제거한 이후에도

+100,000 → -99,999 → + 99,998 ...과 같은 악조건의 경우 역시 시간초과가 발생할 수 밖에 없습니다.

따라서 정렬 과정에서 추가적인 시간 단축 알고리즘을 생각해야 합니다.

위와 동일한 예제로 생각해봅시다.

N = 10이고, 정렬 Order는 위에서 구했던 것처럼+5 → -4 → +3 → -1 입니다.

ex)

10

4 1 5 2 3 10 8 11 15 6

6

3 2

4 5

5 4

3 2

2 1

3 1

1) numArr를 [4 1 5 2 3 10 8 11 15 6] 라고 하고,

numArr와 동일한 값을 갖는 sortedArr를 생성합니다.

2) numArr에서 정렬 대상 값들을 일단 오름차순으로 정렬합니다.

(+5 → -4 → +3 → -1에서 최대 5이므로)

그리고 이제 sortedArr의 빈칸 부분을 효율적으로 채울 것입니다.

3) 아래와 같이 3가지 Index를 설정합니다.

sortedArrIdx 위치에는

오름차순인 경우, 가장 작은 값이 들어갈 것이고

내림차순의 경우, 가장 큰 값이 들어갈 것입니다.

4) sortedArrIdx가 -1씩 이동하면서 적절히 값을 채워 나갑니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%2313415_SortingGame