1  # Push_swap
 2  
 3  이번 과제에서는 스택에 있는 데이터를 한정된 명령어로 최대한 적은 횟수 내에 정렬해야 한다.
 4  
 5  과제에는 정렬해야 하는 int 값들과 두 개의 스택, 그리고 이 스택을 조작하는 명령어 집합이 주어진다.
 6  
 7  ### Trun-in files
 8  `Makefile`, `push_swap.c`, `*.c`
 9  ### 허용 함수
10  `write`, `read`, `malloc`, `free`, `exit`, 내가 작성했던 도구들(ft_printf ...)
11  
12  * 프로그램은 작은 숫자가 스택 a의 top에 오도록 순서대로 정렬해야 하고, 사용한 명령어의 목록을 출력한다.
13  * 명령어는 '\n'으로만 구분되어 출력되어야 한다.
14  * 오류가 발생했을 경우, 표준 출력으로 `Error`와 줄바꿈 문자(`\n`)을 출력해야 한다.
15  	* 오류의 예시로는, 특정 인자값이 정수가 아니거나, 정수보다 큰 인자값이 들어오거나, 중복된 인자가 들어오는 경우이다.
16  
17  ## Rules
18  먼저, 두 개의 스택이 주어진다.
19  * 스택 a는 랜덤한 개수의 (음과 양의) 정수들을 포함하며, 값은 중복되지 안흔ㄴ다.
20  * 스택 b는 비어있다.
21  
22  프로젝트의 목표는 스택 a의 정수들을 오름차순으로 정렬하는 것이다. 다음의 명령어들을 사용할 수 있다.
23  * `sa` (swap a) : 스택 a의 top에 위치한 두 개의 원소의 순서를 맞바꾼다. 스택 a가 비어있거나 원소가 하나만 있을 경우 아무 동작도 하지 않는다.
24  * `sb` (swap b) : 스택 b의 top에 위치한 두 개의 원소의 순서를 맞바꾼다. 스택 b가 비어있거나 원소가 하나만 있을 경우 아무 동작도 하지 않는다.
25  * `ss` : `sa`와 `sb`를 동시에 수행한다.
26  * `pa` (push a) : 스택 b의 top에 위치한 원소 한 개를 스택 a의 top으로 옮긴다. 스택 a가 비어있을 경우에는 아무 동작도 하지 않는다.
27  * `pb` (push b) : 스택 a의 top에 위치한 원소 한 개를 스택 b의 top으로 옮긴다. 스택 b가 비어있을 경우에는 아무 동작도 하지 않는다.
28  * `ra` (rotate a) : 스택 a의 원소를 한 칸씩 위로 옮긴다. 스택의 첫 번째 원소는 맨 마지막 원소가 된다.
29  * `rb` (rotate b) : 스택 b의 원소를 한 칸씩 위로 옮긴다. 스택의 첫 번째 원소는 맨 마지막 원소가 된다.
30  * `rr` : `ra`와 `rb`를 동시에 수행한다.
31  * `rra` (reverse rotate a) : 스택 a의 원소를 한 칸씩 아래로 옮긴다. 스택의 마지막 원소는 맨 첫 번쨰 원소가 된다.
32  * `rrb` (reverse rotate b) : 스택 b의 원소를 한 칸씩 아래로 옮긴다. 스택의 마지막 원소는 맨 첫 번쨰 원소가 된다.
33  * `rrr` : `rra`와 `rrb`를 동시에 수행한다.
34  
35  ## 참고점들
36  * 오류 시 `exit` status 1을 반환하고 종료한다.
37  
38  ## Algorithms
39  
40  Greedy 탐색법을 사용하였다.
41  
42  Greedy 탐색법을 사용하기 전, 스택 a에 무작위로 섞여 있는 숫자들을 pivot을 기준으로 하여, 스택 b로 옮긴다.
43  - 먼저, 프로그램 인자로 들어온 모든 수를 저장하는 정수형 배열 하나를 생성한다.
44  - 정수형 배열의 각 요소들을 연결 리스트의 data로 저장하여, 스택 a에 쌓는다.
45  - 정수형 배열을 버블 소트로 정렬한다.
46  - 정수형 배열의 1/3, 2/3 지점을 pivot으로 삼아, 스택 b가 큰 숫자 덩어리, 중간 숫자 덩어리, 작은 숫자 덩어리로 나뉘어지도록 스택 b에 push 한다.
47  - 전체적으로 한 번 정렬을 함으로써, 스택 b에서 스택 a에 다음으로 정렬할 숫자를 찾는 비용을 최적화하려 하였다.
48  - 스택 a에는 pivot 값을 정렬된 상태로 남겨놓았다.
49  
50  스택 b에 있는 모든 요소를 확인한다. 각 요소가 스택 a에서 어떤 위치를 가지는지(MAX, MID, MIN) 확인하여, 해당 요소가 스택 a에 들어가기 위해선 스택 a를 몇 번 움직여야 하는지 확인한다.
51  
52  하지만 스택 b에 있는 모든 요소를 확인하는 이유는, 스택 b의 가장 상단에 있는 요소가, 스택 a를 최소로 움직이는 요소임을 보장할 수 없기 때문에, 스택 b를 모두 스캔하여, 스택 a를 최소로 움직이는 요소를 찾아서, 스택 b의 가장 꼭대기로 옮겨야 한다.
53  
54  하지만, 스택 a를 최소로 움직이는 요소가 반드시 최적의 답이 아닐 수 있다. 해당 요소를 스택 b의 꼭대기로 옮기느라 발생하는 비용이 더 커질 수 있기 때문이다.
55  
56  따라서, 스택 a를 최소로 움직이는 스택 b의 요소를 구하는 정책은 지켜야 하되, 해당 요소를 스택 b의 상단으로 올려야 하기 때문에, 스택 b를 움직이는 경우도 같이 고려해야 한다.
57  
58  정리하면, 스택 a를 움직이는 횟수 + 스택 b를 움직이는 횟수를 구하여, 가장 적은 경우를 구한 다음, 해당 횟수만큼 스택 a와 스택 b를 돌려주면 된다.
59  
60  이를 스택 b가 빌 때까지 반복한다. 이후, 스택 a는 완전히 정렬된 상태가 되지 않기 때문에(정렬이 이루어지지 않았다는 의미는 아니다. 정렬된 삼각형 모양이 완전하지 않고, 중간이 떨어져 있다는 의미이다), 스택 a도 정렬된 모양으로 만들어준다.
61  
62  이렇게 하면, 적은 명령어의 개수로 스택을 정렬할 수 있다.
63  
64  하지만, 메모리 접근을 많이 하기 때문에, 시간 복잡도는 장담할 수 없다. 그렇기에 정렬 알고리즘이라고 부를 수 있는 가에 대해선 망설여지지만... 과제가 요구하는 사항은 충분하게 충족한다.