[42Seoul] push_swap 풀이 과정

두개의 스택을 이용해서 한 스택에 오름차순 정렬하는 과제인데, 주어진 명령어 들을 이용해 정렬할 요소의 갯수에 따라 주어진 명령어들의 갯수 제한을 두어 최적화를 해야하는 문제이다.

 

./push_swap $ARG

인자로 들어온 명령어들을 A 스택에 담고, B 스택을 하나 더 두고 두 개의 스택을 이용해서 정렬해야 한다.

말은 스택이라고 하지만, 주어진 명령어들을 보면 큐나 덱에 가까운 것 같다

---

sa: stack a의 가장 위에 있는 요소 두개 swap

sb: stack b의 top 두개 swap

ss: sa, sb 동시

pa: 스택 B의 top 요소를 A 로 push

pb: 스택 A의 top 요소를 B 로 push

ra: A의 탑을 제일 뒤로 보냄

rb: B의 탑을 제일 뒤로

rr: ra & rb

rra: 스택 A의 마지막 요소를 top으로 가져옴

rrb: 스택 B의 마지막 요소를 top으로

rrr: rra & rrb

---

이 명령어들을 구현하기 위해 스택에 적용 가능한 여러 가지 자료 구조가 있는데, 배열, 연결리스트, 이중연결리스트, 원형 연결 리스트 등이 있는데 배열은 push 명령이나 ra, rra 등의 명령이 반복되면 연산이 복잡해져서 제외했고, 단일 연결리스트는 마지막 요소를 옮길 때 next 노드를 null로 해주는게 복잡해져서 이중연결리스트로 사용했다.

 

알고리즘은 O(nlogn)의 시간 복잡도를 가진 퀵소트를 베이스로 사용했다.

int main(int argc, char *argv[])
{
    1. 들어온 인자의 유효성 체크
    2. sorting
        pivot 기준으로 A 스택을 분할 (요소가 3개 이하일 때까지)
        sort
        B스택 정렬 -> B스택으로 넘긴 갯수가 2 이하이거나 역순으로 정렬된 경우 A로 push
        	-> B 스택을 피봇 기준으로 분할 (a로 넘긴 값이 3 이상이면 A스택 분할 & 정렬)
}

이런 방식이라고 보면 된다.

원래 퀵소트는

요소가 한개 또는 두개일 때까지 분할하지만, 최적화를 위해 3개 이하일 때는 정렬을 따로 처리했다.

또 이미 정렬된 요소는 확인하지 않아도 되므로 다른 스택에서 넘어온 값만 정렬하도록 했고,

sa -> sa

sb -> sb

ss -> ss

pa -> pb

pb -> pa

ra -> rra

등의 무의미한 명령이 들어오는 경우를 체크해서 동작하지 않도록 했고, 

rb -> ra == rr 이런 식으로 압축 가능한 명령어들은 압축하는 방식을 사용했다.

 

-> 이렇게 하면 500개 일 때 6000개 초반 명령어가 나온다

 

참고

https://profq.tistory.com/31

https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50