BOJ 13415 정렬 게임

입력으로 수열이 주어지고, 그 수열을 정렬할 것인데, 어떻게 정렬할 것이냐면
k개의 (a, b)로 구성된 세트가 입력으로 들어오는데, 한 세트(a, b)는 수열의 1번 수부터 a번 수까지 오름차순으로 정렬하고 수열의 1번 수부터 b번 수까지 내림차순으로 정렬하는 것을 의미한다.
이렇게 k번의 세트에 대해서 모두 정렬이 끝났을 때의 수열을 구하는 문제이다.

수열의 길이가 최대 10만, k값도 최대 10만이라 일일이 다 정렬하다가는 시간초과가 날 것이다. 좀 어려운데, 생각하다 보니 조건에 특이한 점이 있다. 바로 항상 1번 수부터 정렬하는 것이다. 오름차순이든 내림차순이든 주어진 세트(a, b)만큼 정렬하려면 무조건 수열의 처음부터 정렬해야 한다. 그리고 한 세트당 오름차순 정렬을 내림차순 정렬보다 먼저하게 되므로, a<=b인 경우는 오름차순 정렬이 의미가 없다. 그리고 항상 처음부터 정렬하기 때문에, 앞에서 어떻게 정렬했든 간에 앞에서보다 더 큰 값이 나오면 앞에서 정렬한 것이 의미가 없다.

이런 특성을 가지고 잘 생각해보면, 일단 들어오는 k개의 세트(a, b)를 보면서 a<=b인 경우는 b값만 생각하면되고, a>b인 경우는 a, b값 모두 주의깊게 봐야한다. 그리고 a값, b값에 대해서 최대값이 의미가 있으므로 최대값을 구한다. 최대값이 맨 앞에 나온 경우에도 의미가 있는 것이, 예를 들어 가장 큰 값으로 내림차순으로 1~10까지 정렬하고, 그 이후에 더 두번째로 큰 값 1~7까지 오름차순 정렬이 나왔다고 하면 일단 처음에 정렬해놓은 것 중 8~10은 내림차순으로 결정이 되고 바뀌지 않는다. 그렇기 때문에 최대값을 구해서 최대값만큼 정렬을 해놓고... 그 다음으로 큰 값에 대해서 체크해주는 식으로 나가면 될 것 같다.

그럼 k개의 세트(a, b)값들을 입력 받으면서
a<=b인 경우는 b값만 받고 내림차순이란 것과 들어온 순서를 기록하고
a>b인 경우는 a값-오름차순, b값-내림차순, 및 들어온 순서 정보를 기록하는 식으로 받아서
내림차순으로 정렬(1. 값의 크기 기준, 2. 들어온 순서-나중에 온 것이 우선)한 후, 차례로 보면서 배열에 분배하면 될 것 같다.
분배할 땐 미리 원래 수열을 최대값까지 오름차순으로 정렬해놓고, ***
내림차순으로 정렬해놓은 세트값들을 최대값부터 보는데, 가장 나중에 들어온 최대값 이후부터 봐야하므로, 최대값의 들어온 순서이상(더 늦게 들어온)인 것들만 본다. 그리고 또 계속해서 들어온 순서보다 늦게 들어온 것만 봐야한다. 점점 값이 작은 것이 들어올텐데, 앞에 온 것들은 의미 없기 때문이다!!
내림차순 부분이면 다음 오름차순 부분이 오기 전까지 정렬된 수열의 작은 값부터 채워넣고,
오름차순 부분이면 다음 내림차순 부분이 오기 전까지 정렬된 수열의 큰 값부터 채워넣는다.

겨우 겨우 생각했는데, 아직도 헷갈린다. 구현해 봐야겠다.
코드가 너무 지저분해졌다... 그리고 예제만 만족시키고 제출했더니 시간초과가 나서 테스트 케이스를 돌려보는데 무한루프... 계속 고쳐봤는데... 모르겠다. 애초에 구현도 어렵고 코드도 너무 지저분하다. 풀이를 봐야겠다.
------------------------------------------------------------------------------
풀이를 보니 스택을 이용해서 하는 것으로 되어있다... 아... 왜 스택을 전혀 생각 못했을까...생각해 봐야겠다.
생각해보니 스택을 사용하면 위에서 내가 생각했던 것을 훨씬 쉽게 구현할 수 있다.
a<=b인 경우는 b값만 스택에 넣고, a>b인 경우는 a넣고 b넣되, 값을 넣을 때는 스택에 들어 있는 값이 먼저 나온 세트이므로 자기보다 큰지 확인하고 넣어야 한다. 같거나 더 작다면 스택이 비거나 자신보다 더 큰 값이 나올 때까지 빼고 넣는다. 그리고 더 크더라도 방향(오름차순인지 내림차순인지)이 같다면 넣지 않아도 된다. 이런 식으로 채워넣으면 가장 큰 값부터 작은 값순으로 오름차순, 내림차순,...이렇게 방향도 번갈아 스택에 쌓이게 된다.
그리고 내가 위에서 했던 것처럼 구현하려면 스택의 맨 아래값부터 사용해야 하므로 스택을 하나 더 만들어서 옮긴 후 스택의 위에서부터 하나씩 사용하면 된다. 스택의 위에서 뺀 값부터 시작해서 다음값까지 미리 정렬해 둔(가장 큰 세트의 값만큼만) 수열에서 빼서 채워주면 될 것이다.
구현해보자. 확실히 스택을 쓰니까 훨씬 쉽게 구현할 수 있는 것 같다...
내가 구현에서 좀 실수해서 고치고 다시 내서 겨우 AC를 받았다.
참 좋은 문제이다. 스택이라는 자료구조를 이용한느 것도 중요하지만 그 전에 정렬하는 규칙의 핵심을, 원리를 잘 파악하는 것이 매우 중요하다. 스택에 들어있는 값을 이용해서 정답을 구해내는 부분을 위해 생각을 많이 해야한다.
결국 내 힘으로는 못풀었지만... 많이 배운 문제였다. 꼭 나중에 다시 풀자.