푸시스왑

오젼·2022년 6월 2일

push_swap 개요

기본적으로 4개의 동작으로 설명할 수 있음 push, swap, rotate, reverse rotate

push	한 스택에서 pop한 원소(top원소)를 다른 스택에 push	[1] , [2 3 4 5] --> [] , [1 2 3 4 5]
swap	스택의 top과 top 다음 원소를 swap	[2 1 3 4 5] --> [1 2 3 4 5]
rotate	스택을 위쪽으로 회전. top원소가 가장 아래 원소로 가게 됨	[5 1 2 3 4] --> [1 2 3 4 5]
reverse rotate	스택을 아래쪽으로 회전. 가장 아래 원소가 top으로 가게 됨	[2 3 4 5 1] --> [1 2 3 4 5]

a스택에서 b스택으로 pb를 이용하여 원소를 옮긴다.
이 때 b스택이 내림차순 정렬이 되도록 적절하게 operation을 사용한다.
내림차순 정렬이 된 b스택의 원소를 다시 pa를 통해 a스택으로 옮긴다.
그럼 a스택은 오름차순 정렬이 된 상태가 된다.
b스택을 내림차순으로 정렬하는 방법은 다음과 같다.
1. pb하려는 값보다 더 작은 값이 b에 있다면 그 중 가장 큰 값이 top에 오도록 한다.
2. pb하려는 값보다 더 작은 값이 b에 없다면 b에서 가장 큰 값이 top에 오도록 한다.

pb를 하기 전 a스택의 원소 중 명령어가 가장 최소가 되는 경우를 찾는다. (choose_best_elem)
1. a의 top원소를 pb하기 전 rb 8번이 필요하다. --> ra 0번 rb 8번 = 8 op
2. a의 두 번째 원소를 pb하기 전 rrb 4번이 필요하다. --> ra 2번 rrb 4번 = 6 op
3. a의 세 번째 원소를 pb하기 전 rb 2번이 필요하다. --> ra 3번 rb 2번 --> rr 2번 ra 1번 = 3 op
* 즉, 세 번재 원소를 pb하는 것이 가장 best다.
3개 이하의 원소에서는 하드코딩을 통해 명령어 개수가 최소화 된 상태로 만든다.
- 경우의 수: [3 2 1][1 3 2] [2 1 3][2 3 1] [1 3 2][2 1]
- a스택에서 b스택을 옮길 때 가장 큰 원소, 그 다음 큰 원소, 그 다음 큰 원소 3가지는 놔두고 pb를 통해 b에서 나머지 원소를 내림차순 정렬시킨 다음 a에서는 하드코딩된 경우의 수로 명령어를 처리한다.

main 인자로 받은 문자열을 integer형으로 바꿔 스택에 쌓아줄 수 있게 get_values 함수를 구현한다.
이 때 숫자꼴이 잘못 되었거나 integer범위를 초과하거나 중복인 원소가 있는 경우엔 standard error로 에러문을 출력하고 중도 종료한다.
push_swap operation을 처리하기 위해 op파일 안에 기본 작동인 push, swap, rotate, reverse_rotate에 관한 함수를 만든다.
이후 do_op파일 안에 문자열로 명령어를 받아 처리하는 do_op함수를 구현한다.
a스택의 원소가 3개 이하인 경우는 하드코딩해 둔 simple_sort로 들어가 처리하게 한다.
3개를 초과하는 경우 a스택에 가장 큰 값, 그 다음 큰 값, 그 다음 큰 값 세 개는 남겨두고 pb를 통해 b에 내림차순으로 원소를 보낸다.
b의 max를 top으로 보내 완전한 내림차순을 만든 다음 a에 남아있는 세 원소도 simple_sort를 통해 정렬해준다. 이후 pa를 통해 b에 있는 원소를 모두 차례대로 a에 보내면 a가 오름차순으로 정렬된다.

checker는 get_next_line으로 명령어를 한 줄씩 읽어온 다음 구현해 두었던 do_op를 사용해 차례대로 명령어를 실행시키면 된다. 단, checker에서 do_op를 할 때는 명령어를 출력하지는 않는다.
이후 명령어 실행이 다 끝난 상황에서 a가 오름차순 정렬이면서 b가 비어있는 상태라면 OK를, 하나라도 만족시키지 못하면 KO를 출력한다.
잘못된 명령어인 경우 error처리를 해줘야 하기 때문에 do_op함수에서 push_swap명령어가 아닌 다른 문자열이 들어오면 반환값을 달리해 잘못된 명령어인지 알 수 있도록 한다.