[백준] 13415 정렬 게임

13415번: 정렬 게임

풀이 아이디어

 

구현을 통해서 입력을 받을때마다 정렬을 하게 된다면  O(N*NLog(N))이 걸리게 된다.

N이 10만이기 때문에 구현으로만 풀면 시간초과를 받게 된다.

 

이 문제의 핵심은 정렬하는 대상이 반드시 1부터 시작 한다는 것과

이전에 실행했던 정렬보다 같거나 큰 범위로 정렬하게 된다면 이전에 실행했던 정렬이 아무런 의미가 없다는 점이다.

 

먼저 후자를 살펴보자면

 

인덱스 1 ~ 3 을 정렬해봤자 이후 인덱스 1 ~ 4를 정렬하면 1 ~ 3 정렬은 아무런 의미가 없다는 점이다.

즉 이 문제에서 결과에 유의미한 영향을 끼치는 정렬은

정렬 입력값을 받았을 때

가장 큰 수 부터 내림차순으로 정렬된 정렬값만이 결과에 영향을 끼친다.

 

만약

숫자를 

1 2 3 4 5 6 7 8 9 10으로 받고

 

정렬 입력값이

4

1 5 9 10 4 8 5 6 이라면 이 중

10 8 6 만 계산하면 된다는 것이다.

 

물론 정렬 입력값을 내림차순으로 입력받을 수도 있다는 점 때문에 단순 시간 복잡도에는 아무런 의미가 없다.

 

다만 시작지점이 1로 고정되어 있다는 점 덕분에

정렬 입력값들은 서로에 대해서 시작지점이 동일한 부분집합이다.

이를 인지한다면 다음과 같은 연산이 가능하다.

 

 

10 8 6을 정렬을 진행하게 될경우

 

 

10의 정렬이 진행될경우

10 ~ 9번째 칸은 오름차순이나 내림차순에 따라서

1 2 혹은 9 10을 받게 된다.

 

8의 정렬인 경우에는

10의 정렬에 따라서

3 4 또는 1 2   혹은  9 10 또는 7 8 을 넣게된다.  

 

결론적으로

 

처음 입력 받은 수열에 대해서 정렬을 한번 진행한다음

오름차순이나 내림차순에 따라서

양 끝부분 중 택 1을 하여 출력값에 옮겨 담으면 된다.

deque를 사용할 경우 O(N)만으로 계산이 가능해진다.

 

시간복잡도

입력 값 정렬하기 O(N logN)

정렬 계산 O(N)

 

= O(N log N)

 

시행 착오

 

반드시 1부터 시작한다는 조건을 제대로

확인하지 않아서 막막했던 문제였다.

 

최적화 해보기

 

정렬을 한번 걸치지 않고서는 풀기 불가능하다.

N

1 3...N... 2 4 ... N-1

1

N N 만 주어지더라도 반드시 정렬을 한번은 걸쳐야 한다.

 

따라서 더 빠르게 풀 수는 없을 것 같다.