개념

스택(연결리스트로 구현한) 2개를 이용하여 숫자를 정렬해야 하는데, 아래 연산만 사용하여야 한다.

과정

다른 풀이법들을 보니까 스택을 chunk 여러 개로 나눠서 quick 정렬을 모방한 방법을 사용하던데 나 역시 이 방법을 시도했으나 막히기도 했고, 이 방법으로 왠지 풀릴 것 같은데? 하고 시도해보게 되었다. 이러한 영감을 받은데는 https://medium.com/@jamierobertdawson/push-swap-the-least-amount-of-moves-with-two-stacks-d1e76a71789a 가 큰 역할을 했다.

풀이

풀이에 앞서 연결리스트를 이중 연결리스트로 구현하였고, index 라는 변수를 추가해서 정렬하기 전 해당 숫자가 몇 번째로 큰 숫자인지를 계산해두었다. (연산에는 큰 의미 없으나 디버깅하는 입장에서 보기가 편하더라)

그리고 어떠한 숫자를 top에 올리려고 할 때, 해당 숫자가 top에 가까이 있으면 r 연산을, bottom에 가까이 있으면 rr 연산을 사용하는 것을 기본으로 한다. (그렇지 않다면 n개의 노드가 있는 스택에서 bottom에 있는 숫자를 top에 올리려면 r 연산을 (n - 1)번 수행해야 할 것이다).

문제에서 요구하는 정답은 스택 a에 가장 작은 값이 top으로, 가장 큰 값이 bottom으로 오는 오름차순으로 정렬하는 것이었다. 내가 생각한 방법은 우선 스택 b에 내림차순으로 정렬하고, pa를 사용해 a로 옮기는 것이었다.

우선 가장 쉽게 생각할 수 있는 방법인 스택 a에서 최댓값을 찾아 스택 b로 옮기는 방법을 채택하였으나 아니나 다를까 시행 횟수가 문제에서 요구하는 횟수를 아득히 뛰어 넘었다.

그 다음으로 시도한 방법은 가장 적은 연산으로 제 자리를 찾아가는 숫자를 찾는 방법이었다.

예를 들어 설명하자면,

  10

   6

   5             8 

   3             9

   7             1

   2             4

   A             B

10이 B에서 제 자리를 찾아가려면 rb rb 연산 2회가 필요하다.

6이 B에서 제 자리를 찾아가려면 ra 연산 1회가 필요하다.

5이 B에서 제 자리를 찾아가려면 ra ra 연산 2회가 필요하다.

3이 B에서 제 자리를 찾아가려면 ra ra ra rrb 연산 4회가 필요하다.

7이 B에서 제 자리를 찾아가려면 rra rra 연산 2회가 필요하다.

2이 B에서 제 자리를 찾아가려면 rra rrb 연산 2회가 필요하다.

최소 연산으로 제 자리를 찾아 갈 수 있는 6을 B로 넘겨주면

       5           6

       3           8

       7           9

       2           1

       10          4

       A           B

위와 같은 형태가 된다.

“제 자리”를 찾는 방법은 top이 넘기려는 숫자보다 크고, bottom이 넘기려는 숫자보다 작은 상태가 제 자리를 찾은 상태이다.

하지만 넘기려는 숫자가 스택 B에서 최솟값이거나 최댓값인 경우 사이에 끼워넣기가 불가능한데, 이 경우에는 스택 B를 최댓값이 top에 오도록 정렬을 해주면 된다.

이와 같은 방법으로 하면 500개의 랜덤 숫자를 처리하는데 평균적으로 6000번의 연산을 하게 된다.