PUSH_SWAP 과제

아래 두 자료를 주로 참고하여 코드를 작성하였다.

 

1. 슬랙에 minckim님 께서 올려주신 push_swap가이드

2. https://medium.com/@jamierobertdawson/push-swap 번역된 글

 

과제의 감을 잡고, 진행하는데 있어서 정말 도움이 많이 되었다.

 

간단 과제 설명

a 스택, b스택이 주어진다.

문제에서 주어진 액션(sa, sb, ss, pa, pb, ra, rb, rr, rra)을 사용하여 스택 a를 정렬시킬 수 있는 액션들을 출력해야한다.

 

$> ./push_swap 2 1 3 6 5 8
sa
pb 
pb
pb 
sa
pa 
pa
pa

2 1 3 6 5 8 을 정렬시키기 위해서는 위와 같이 액션을 호출하면 정렬 할 수 있다.

 

 

동작을 시각화로 살펴보자

사실 문제만 봐서 이해가 안가니 push_swap에서 허용된 액션만 이용하여 정렬되는 과정을 살펴보자. 

 

 

 

위 동영상은 내가 작성한 push swap 프로그램을 push_swap_visuailizer을 사용하여 시각화한 것이다.

git: https://github.com/o-reo/push_swap_visualizer

 

찾아본결과 청크? 로 나누는 방식도 있고, 퀵 소트를 이용한 방식도 있고, 병합정렬을 이용한 방식들이 있었다. 

해결 방법이 여러가지가 있으므로, 동영상에서 나오는 정렬방법에 너무 얽매지 않았으면 좋겠다.

 

 

예외처리

- 중복되는 숫자

- int 범위가 넘는 수 (int 범위: -2147483648 ~ 2147483647)

- 아무것도 입력받지 않았을때, 아무것도 출력하지 않기.

 

 

코드 개발 순서

1. 양방향 링크드리스트 만들기 (완료)
2. main에서 인자값을 입력받을 수 있게 만들기 (완료)
3. 비어있을때, 인자가 숫자가 아닐때, 과제의 요구사항에 맞춰 예외처리 하기(완료)
4. 각 커맨드 액션들 구현하기 (완료)
5. 커맨드 링크드리스트 만들기 (완료)
6. 커맨드 리스트 저장 및 출력 (완료)
7. 정렬로직 구현하기 - 재귀 (완료)
8. push_swap 인자값이 " " 일 때 처리하기(완료)
9. 검토

꼭 양방향이 아니어도 되고, 커맨드를 링크드리스트로 만들 필요 또한 없다.

개인마다 코딩 스타일이 있기 때문에 참고용으로 올려놓았다.