팬 케이크 정렬 : 위에서부터 k개를 뒤집는다.

 팬케이크 정렬은 유튜브에서 영상으로 한 번 쯤은 보셨을 겁니다. 이것을 최소한으로 뒤집는 횟수를 구하는 것은 경시 대회 이상에서 나올 만한 문제입니다. 우리는 단지, 어떻게 잘 뒤집어서 정렬을 잘 시키면 됩니다. 팬 케이크 더미에서는 위에서 k개만 뒤집을 수 있습니다. 단, k는 총 갯수보다 작을 거에요.

 

 갯수를 n개라고 한다면 2n-3번 이하 뒤집어야 합니다. 이 때에는 어떻게 해야 할까요?

 

 

---

 사실, 잘 모르겠습니다. 일단, 1회전이 끝날 때 마다, 2회의 단위 연산을 수행해야 한다는 것은 알겠습니다. 그러면 한 회전마다 어떤 일이 일어나면 좋을까요?

 

 

  팬 케이크가 이런 식으로 쌓여 있다고 생각해 봅시다. '위에서 k개를 뒤집는다'는 연산 특성상, k가 n이 아니라면, 맨 아랫쪽에 있는 것은 움직이지 않습니다. 그러면 무엇인가를 맨 아래로 보내야 한다는 것은 맞아보입니다. 한 턴마다요. 그러면 그 대상을 어떻게 찾아야 할까요?

 

 일단, 4가 맨 밑에 있지 않아요. 그러면 우리는, 4를 맨 아래로 보내야 한다는 사실 또한 부정하지 못할 겁니다.

 

 

 4가 있는 위치는 2입니다. 먼저 4를 맨 위로 보내려면, 위에서 2개를 뒤집는 방법밖에 없습니다.

 

 

 그 다음에 어떻게 하면 좋을까요? 4가 맨 위에 왔습니다. 이것은 오름 차순으로 정렬하려고 할 때, 가장 낮은 우선 순위를 가지는 것입니다. 제가 칠한 부분을 뒤집어 버리면, 4는 맨 밑으로 가게 되어 있습니다.

 

 

 그러면 1회전이 끝나게 됩니다. 뒤에서부터 정렬이 된다는 것은 버블과 매우 흡사합니다. select 하는 건 선택과 닮았고요. 그런데 무엇을 선택했나요? n개를 정렬해야 할 때, 1번째 턴에서는, n을 찾고, 2번째에서는 n-1을 찾고, ... 이런 식으로 찾아서, 맨 앞으로 올리기 위해 뒤집고, 맞는 위치에 배치 하기 위해서 뒤집고. 이렇게 한 턴마다 2회씩 뒤집는다. 이렇게 정리하시면 좋을 듯 싶습니다.

 

 이제 계속 가 봅시다.

 

 

 3은 이미, 위치에 맞게 가 있습니다. 그러니, 뒤집고, 다시 또 뒤집을 필요가 없어요. 건너 뜁니다.

 

 

 그런데, 2가 제 위치에 있지 않다는 것을 알 수 있어요. [2, 1]에서는, 2가 제 위치에 있지 않은 수 중에서 제일 큽니다. 따라서, 2를 선택합니다.

 

 

 그러면, 2를 맨 위로 올립니다. 그리고, 2는 1번째가 아닌 2번째 위치로 가야 하기 때문에, 위에서 2개를 뒤집습니다.

 

 

그러면, 정렬을 끝마칠 수 있습니다. 핵심은, i번째 턴에서, n-i+1이 제 위치에 있으면 바로 i+1번 턴으로 넘어가고, 그렇지 않으면, n-i+1을 위로 올리고, 그 수를 위치에 맞게 밑으로 이동시키면 됩니다.

 

 

---

 그러면 여기서 질문 하나 해 봅시다. 2n-3회만 뒤집으면 sorting이 가능할까요? 일단 케이크가 n개 있다고 해 봅시다.

 

 

 그러면 n-1회전 돌면 2번부터 n번까지는 정렬이 되어 있을 겁니다. 이 때 1은 sorting을 할 필요가 없습니다. 1회전 당, 2회의 단위 연산을 하기 때문에, 그냥 2보다 크거나 같고 n보다 작거나 같은 k에 대해서, k를 위로 올리고 다시 밑으로 내리는 연산을 했을 때, 총 2(n-1)회의 연산을 하게 됩니다. 2n - 2는 2n - 3보다 딱 1이 더 큽니다.

 

 그런데, 사실 이것만 보더라도, 2n - 3회번 정도만 뒤집기 연산을 하면 sort가 된다는 것을 알 수 있는데요. 2(n-2)번 filp을 했을 때, 상황은 둘 중 하나일 겁니다.

 

 

 이렇게 되어 있거나, 아니면 1과 2가 역순으로 되어 있거나. 둘 중 하나입니다.

 

 

 그러면 1, 2, ... 순으로 되어 있는 경우에는 굳이 뒤집을 필요가 없어요. 2, 1, ... 이런 경우에는, 위에서부터 2개를 filp 하면 됩니다. 즉, 2n - 4 + 1 = 2n - 3회만 filp를 하면 sort가 되는 셈입니다.

 

 

---

 이것을 그대로 코드로 구현해 봅시다.

 

 

 배열의 크기가 n이라면, 배열에는 1부터 n까지의 수가 딱 1번씩만 들어옵니다. 먼저 work를 잘 볼 필요가 있는데요. 이는 arr[i] != i인 가장 큰 i를 찾는 함수입니다.

 

 

 여기서, work가 -1이라면, arr[i] != i인 i가 없는 경우입니다. 이 때에는 그냥 sort가 되었으니 빠져 나옵니다. 그렇지 않다면, 뒤집는 것을 2번 수행해야 할 건데요. 이 때, work는, arr[i] != i이면서, 가장 큰 i가 있는 위치를 돌려줍니다.

 

 

 그러면 work의 리턴 값이 lo였고, [0, lo] 구간을 뒤집었을 때, [0, lo]에서 가장 큰, 그러니까 우선 순위가 가장 낮은 원소는 arr[0]일 겁니다. 이 값을 arr[0]번째로 보내려면, [0, arr[0]]을 뒤집어버리면 될 겁니다. 27번째 줄이 그러한 일을 수행합니다. 이걸 구대로 구현하면 2759번 문제를 풀 수 있습니다.