Budnarae

push_swap

5 min read

push_swap

자료구조, 알고리즘

두 개의 스택과 제한된 연산만을 사용하여 뒤섞인 숫자 배열을 정렬하는 과제이다. 단순히 정렬이 되는 것에 그치지 않고, 사용하는 연산의 횟수를 최소화하는 전략을 설계하는 것이 핵심이다.

개요

스택 a와 스택 b, 두 개의 스택이 주어진다. 초기 상태에서 정렬할 숫자들은 모두 스택 a에 있으며, 스택 b는 비어 있다. 후술할 연산들만을 사용하여 최종적으로 스택 a에 숫자들이 오름차순으로 정렬된 상태를 만들면 된다. 입력하는 숫자들은 서로 중복되지 않아야 한다.

push_swap을 실행하면 정렬에 필요한 연산의 나열을 출력한다.

./push_swap 5 2 1 4 7 6 3
 
sa
pb
rra
pb
sa
...

push swap visualizer를 활용하면 출력된 연산 시퀀스가 스택에 어떻게 적용되는지 시각적으로 확인할 수 있다. WSL 환경에서는 아래 명령어로 출력 결과를 클립보드에 복사한 뒤 붙여넣으면 된다.

./push_swap [뒤섞인 숫자 나열] | xclip -selection clipboard

허용 연산

이 과제에서 사용할 수 있는 연산은 다음과 같다. 일반적인 스택과 달리 회전(rotate) 연산이 추가된 별도의 자료구조라 볼 수 있다.

연산동작
sa스택 a의 맨 위 두 요소를 교환. 요소가 하나 이하면 아무것도 하지 않는다
sb스택 b의 맨 위 두 요소를 교환. 요소가 하나 이하면 아무것도 하지 않는다
sssa와 sb를 동시에 수행
pa스택 b의 맨 위 요소를 꺼내 스택 a의 맨 위에 넣는다. 스택 b가 비어 있으면 아무것도 하지 않는다
pb스택 a의 맨 위 요소를 꺼내 스택 b의 맨 위에 넣는다. 스택 a가 비어 있으면 아무것도 하지 않는다
ra스택 a의 모든 요소를 위로 1칸 이동. 맨 위 요소가 맨 아래로 간다
rb스택 b의 모든 요소를 위로 1칸 이동. 맨 위 요소가 맨 아래로 간다
rrra와 rb를 동시에 수행
rra스택 a의 모든 요소를 아래로 1칸 이동. 맨 아래 요소가 맨 위로 온다
rrb스택 b의 모든 요소를 아래로 1칸 이동. 맨 아래 요소가 맨 위로 온다
rrrrra와 rrb를 동시에 수행

구현 내용

정렬 알고리즘 및 연산 최적화
단순히 정렬이 완료되는 것만으로는 부족하며, 입력 크기에 따라 허용되는 최대 연산 횟수 기준이 있다. merge sort를 스택 연산에 맞게 응용하여 구현했다. rr, rrr 같이 두 스택을 동시에 조작하는 연산을 적극 활용하여 연산 횟수를 줄인다.

입력 검증
중복된 숫자, int 범위를 벗어난 숫자, 숫자가 아닌 입력 등 예외 상황을 처리한다.

보너스: checker 프로그램
push_swap이 출력한 연산 시퀀스를 표준 입력으로 받아, 해당 연산들을 실행했을 때 실제로 정렬이 올바르게 완료되는지 검증하는 checker 프로그램을 구현했다.

./push_swap 5 2 1 4 7 6 3 | ./checker 5 2 1 4 7 6 3
OK

Graph View