두 개의 스택이 있다. 스택 A에는 랜덤한 순서의 숫자들이 있다. 두 스택을 이용하여 스택 A의 숫자들을 정렬하자. 이때 사용 가능한 명령어들은 다음과 같다.
sa (swap a): Swap the first 2 elements at the top of stack a.
Do nothing if there is only one or no elements.
sb (swap b): Swap the first 2 elements at the top of stack b.
Do nothing if there is only one or no elements.
ss : sa and sb at the same time.
pa (push a): Take the first element at the top of b and put it at the top of a.
Do nothing if b is empty.
pb (push b): Take the first element at the top of a and put it at the top of b.
Do nothing if a is empty.
ra (rotate a): Shift up all elements of stack a by 1.
The first element becomes the last one.
rb (rotate b): Shift up all elements of stack b by 1.
The first element becomes the last one.
rr : ra and rb at the same time.
rra (reverse rotate a): Shift down all elements of stack a by 1.
The last element becomes the first one.
rrb (reverse rotate b): Shift down all elements of stack b by 1.
The last element becomes the first one.
rrr : rra and rrb at the same time.
이 과제에 입력 처리, 자료구조 선택, 오류 처리 등 여러가지 포인트들이 있지만 핵심은 알고리즘 선택이다.
기본적인 아이디어는 정렬된 삼각형을 합치면(merge하면) 하나의 큰 정렬된 삼각형을 얻을 수 있다는 것이다. 2개를 합칠 수도 있지만 아래와 같이 3개의 삼각형을 합치면 $A(n) = O(\log_2n)$에서$A(n) = O(\log_3n)$가 된다. (4개는 불가능)
그럼 세개의 삼각형은 어떻게 만들까? 아래의 과정을 통해 만들어 진다.
즉, 맨 왼쪽과 같은 모양을 만들면 맨 오른쪽과 같은 모양을 만들 수 있다는 것이다. (merge과정에서 불필요한 연산을 줄이기 위해 위 링크와는 과정을 다르게 짰다.)
그럼 이제 삼각형을 분할해 나가며 하나의 삼각형에 적당한 개수의 원소가 들어있을 때까지 반복하여 최종 형태를 만들면 된다. (분할 정복)
두개의 스택을 이용해 정렬해야 하는 상황이므로 그냥 D&C하듯이는 힘들고 이 패턴을 동적계획법을 이용해 계산할 수 있다. 아래의 점화식을 이용하면 된다. (여기서 i는 단계, j는 삼각형 번호. 삼각형이 하나만 있는 것이 0단계이다.) 음수는 역삼각형을 의미한다.
$j < 3^{i-1}\ or\ 2\times3^{i-1} \le j < 3^i$
pattern[i][j] = pattern[i - 1][j] / 3
그냥 그대로이다.
$3^{i-1} \le j < 3^{i-1}\times {2\over3}$
pattern[i][j] = pattern[i - 1][j - tri_num / 9] / 3 + 나머지
어차피 나중에 넘기면서 뒤집히기 때문에 뒤집지 않고 그대로 받는다.
$3^{i-1}\times {2\over3} \le j < 2 \times 3^{i-1}$
pattern[i][j] = (-1) * (pattern[i - 1][tri_num / 3 * 2 - 1 - j] / 3) - 나머지
뒤집은 상태이다.