push_swap
SUBJECT
초기 상태
스택 a : 랜덤 개수의 양의 정수와 음의 정수가 들어있다.
스택 b : empty
→ 스택 a의 수를 오름차순으로 정렬하는 것이 목표입니다.
아래의 명령어를 통해서 정렬시켜야 합니다.
sa : swap a - 스택 a의 top에 위치한 두 개의 원소의 순서를 맞바꿉니다.
스택 a가 비어있거나 원소가 1개만 있을 때는 아무 동작도 하지 않습니다.
sb : swap b - Swap the first 2 elements at the top of stack b.Do nothing if there is only one or no elements).*
sb : swap b - 스택 b의 top에 위치한 두 개의 원소의 순서를 맞바꿉니다.
스택 b가 비어있거나 원소가 1개만 있을 때는 아무 동작도 하지 않습니다.
ss : sa and sb at the same time.*
ss - sa와 sb를 동시에 수행합니다.
pa : push a - Take the first element at the top of b and put it at the top of a.Do nothing if b is empty.*
pa : push a - 스택 b의 top에 위치한 원소 한 개를 스택 a의 top으로 옮깁니다.
스택 b가 비어있을 경우에는 아무 동작도 하지 않습니다.
pb : push b Take the first element at the top of a and put it at the top of b.Do nothing if a is empty.*
pb : push b - 스택 a의 top에 위치한 원소 한 개를 스택 b의 top으로 옮깁니다.
스택 a가 비어있을 경우에는 아무 동작도 하지 않습니다.
ra : rotate a - Shift up all elements of stack a by 1.The first element becomes the last one.*
ra : rotate a - 스택 a의 원소를 한 칸씩 위로 옮깁니다.
스택의 첫 번째 원소는 맨 마지막 원소가 됩니다.
rb : rotate b Shift up all elements of stack b by 1.The first element becomes the last one.*
rb : rotate b - 스택 b의 원소를 한 칸씩 위로 옮깁니다.
스택의 첫 번째 원소는 맨 마지막 원소가 됩니다.
rr : ra and rb at the same time.*
rr : ra와 rb를 동시에 수행합니다.
rra : reverse rotate a - Shift down all elements of stack a by 1.The last element becomes the first one.*
rra : reverse rotate a - 스택 a의 원소를 한 칸씩 아래로 옮깁니다.
스택의 마지막 원소는 맨 첫 번째 원소가 됩니다.
rrb : reverse rotate b - Shift down all elements of stack b by 1.The last element becomes the first one.*
rrb : reverse rotate b - 스택 b의 원소를 한 칸씩 아래로 옮깁니다.
스택의 마지막 원소는 맨 첫 번째 원소가 됩니다.
rrr : rra and rrb at the same time.
rrr : rra와 rrb를 동시에 수행합니다.
push_swap 과제를 해결하는 방법은 매우 다양합니다. 퀵 소트, 머지 소트, 그리디, 모래시계 등등.. 다양한 방법이 존재하지만, 저는 이 과제가 시간복잡도가 아닌 단순히 최소한의 명령을 수행하는 과제라고 생각하여 그리디를 통해서 과제를 해결하기로 했습니다.
Step. 1 - 리스트 구현
먼저 숫자를 담아낼 수 있는 공간을 구현했습니다. 서브젝트 상에서는 스택이라 설명이 되어있지만, 스택의 head와 tail에 각각 원소가 삽입, 삭제가 되어야 한다는 점에서 덱과 같은 기능의 양방향 연결리스트로 구현하게 되었습니다.
Step. 2 - 명령어 구현
argv로 들어온 인자들을 리스트에 담아주어야 하므로 리스트에 삽입을 할 수 있는 push() 함수를 만들고, 삭제를 할 수 있는 pop()함수를 만들었습니다. 이렇게 만들어진 push, pop을 적절하게 이용한다면, 위의 pa, pb, sa, sb 와 같은 명령어를 쉽게 구현할 수 있습니다.
Step. 3 - Parsing
Step. 2로 명령어 들이 잘 구현이 되었다면, 이제 argv로 들어온 인자가 유효한 인자인지를 판단하여 유효하다면 리스트에 push를 해줘야 합니다. argv가 유효하다는 기준은 아래와 같습니다.
- 정수 범위 이내의 숫자 인자
- 문자가 포함되지 않은 인자
- 정렬이 되어 있지 않은 인자들
- 빈 문자열이 아닌 인자 ex) ““
- 큰 따옴표 안에 여러 인자들이 포함되어 있다면 각각 위의 유효 조건을 충족할 수 있는 인자
위의 조건들을 충족하지 않는 인자들이 입력될 경우 에러메시지를 표시해야 합니다.
저의 경우 1, 2 조건을 확인하는 방법은 먼저 들어온 인자를 ft_atoi 함수를 통해 숫자로 바꾼뒤 이를 다시 ft_itoa함수로 문자열로 변환합니다.
이렇게 변환된 문자열이 argv와 같다면 유효하다고 판단하였습니다.
예를 들어 설명하면 “12ab” 가 들어올 때 ft_atoi함수에서 12만 남게 되고 이를 다시 itoa한다면, “12”가 됩니다. “12” ≠ “12ab” 이므로 이는 유효한 인자가 아니게 되는 것이죠.
2번 조건의 경우도 atoi 함수에서는 정수 범위 밖의 수는 오버플로우가 일어나게 되므로 원본 argv랑은 값이 다르게 됩니다.
3번 조건은 일단 인자가 1, 2 조건을 충족한다면 스택에 일단 삽입한 후 정렬 체크 함수를 만들어 확인했습니다.
4번 조건은 “” 를 ft_split 함수를 통해 arr배열에 삽입이 된다면, arr[0]의 값이 남아 있지 않게 되는 것을 이용하여 확인 하였습니다.
5번 조건 또한 ft_split 함수를 통해 배열에 삽입하고 위의 조건들을 확인하였습니다.
Step. 4 - 인덱싱
이제 유효한 인자들만 입력받아 스택a 에 잘 삽입이 되었습니다.
이제 정렬을 해야겠죠. 먼저 저는 스택A에 있는 노드들을 인덱싱하는 과정을 진행했습니다.
제가 말하는 인덱싱은 만약 5 4 3 2 6 이 입력이 되었다면 이 수들을 작은 수 부터 0부터 시작되는 수들로 치환을 해주었습니다. 3 2 1 0 4 이런 식으로 말이죠.
이렇게 인덱싱을 해주는 이유는 다음 step 6에 나오게 될겁니다.
Step. 5 - 2, 3, 4, 5 최적화 함수만들기
3개의 원소가 입력되었을때는, 경우의 수가 얼마 없습니다. 따라서 명령어들을 하드코딩하는 것이 더욱 효율적일 수 있습니다.
4, 5 개의 원소는 경우의 수가 꽤 많기는 하지만 먼저 만든 3개의 원소를 정렬해주는 함수를 이용한다면, 쉽습니다. 먼저 4,5개의 원소 중 가장 작은 값을 찾아 a스택의 top으로 ra 시킨 뒤, pb 해줍니다.
5개 원소는 이 과정을 한번 더 진행하고, a스택에 남은 3개의 원소를 위의 함수로 정렬해준 뒤, b스택의 원소를 다시 불러오면 아마 정렬이 되어있을 겁니다.
Step. 6 - 3분할하여 넘기기
이제 인덱싱을 해주었기 때문에 스택A 리스트는 제일 작은 값은 0, 가장 큰 값은 (리스트의 크기 - 1) 이 되어있을 겁니다.
다음으로는 스택 A에 숫자 3개만 남기고 나머지는 전부 B스택으로 넘겨줄겁니다.
3개를 남기는 이유는 스택B에 있는 수들을 하나씩 넘길 때, 스택 A의 수들을 기준으로 옮기기 때문에 기준이 되는 피봇역할을 하도록 남겨 주었습니다.
이제 진짜 나머지 수를 b스택에 넘겨 주어야 겟죠? 저는 이때, 전체사이즈 * 2/3 보다 큰수를 먼저 넘겨 주었습니다. 이게 아까 이전에 인덱싱을 해준 이유입니다. 인덱싱을 하지 않았다면, 전체값 중 상위 33퍼센트 값을 가진 수들을 찾기 매우 까다로웠을 겁니다.
이렇게 상위 33퍼센트의 값들이 넘어가면 전체사이즈 * 1/3 보다 큰 수 상위 66퍼센트에 해당되는 수가 넘어 가게 됩니다.
그리고 나머지 하위 33퍼센트를 넘기게 되는데, 이전에 전체사이즈 * 2/3, 전체사이즈 * 1/3 의 값에 해당되는 값들은 아마 넘어가지 않았을 겁니다. 이 두 숫자를 포함해서 스택a의 사이즈가 3이 될때까지 값들이 다 스택B로 넘어가게 됩니다.
이러게 남은 숫자 3개를 하드코딩 해두었던 함수로 정렬시킵니다.
3분할을 한 이유는 3분할을 하게 될 경우 비슷한 범위의 수들이 근처에 위치하게 되면서, 다음스텝에 나오는 회전횟수의 최솟값이 더욱 적어지는 효과를 얻을 수 있습니다.
Step. 7 - 회전횟수 최솟값찾기
이제 스택b에 있는 원소를 a스택에 맞는 위치에 넣어야 합니다. 우리는 스택의 top에서 top으로만 원소를 옮길 수 있으므로, b의 가장 위 원소가 a스택에 잘 들어갈 수 있도록 a스택을 회전시켜야 합니다.
예를 들어 설명하자면,
이렇게 b의 원소가 a로 가기위한 스택a의 회전수를 구했습니다. 그런데 만약 B의 top원소보다 그 아래 원소를 옮길 때, 회전수가 더 적다면 그 원소를 먼저 옮기는게 합리적이겟죠..???
추가설명...ㅠ
B스택 top이 A스택으로 가기 위해서는 ra()를 10번해야한다고 합니다.
반면, B스택 top 다음 원소가 A스택으로 가기 위해서는 ra() 3번이라고 한다면, 이 원소가 B스택의
top으로 가기위한 rb() 1번 까지 더해서 총 4번의 명령으로만 A스택으로 옮길 수 있는 것이죠이 과정을 b스택을 다돌면서 ra+rb 의 수가 최소인 인덱스를 찾습니다.
이렇게 A스택의 회전수와, B스택의 회전수를 구했으니 이대로 회전만 시켜주면 됩니다.
하.. 근데 여기서 조금 더 명령 횟수를 줄이기 위해서 해야할 것이 있습니다.
만약에 B스택에서 옮겨야 할 값이 B스택의 중간보다 아래에 있다면 rrb를 하는게 더 이득이겟죠..?
그래서 만약에 b_index ≥ stack_b→size / 2 라면 b_index - stack_b→size 를 해줍니다. 이러면 음수가 나오겟죠. 이 음수가 0이 될만큼 rrb해주면 됩니다. 스택 a도 마찬가지입니다.
Step. 8 - pb()
이제 각 최솟값을 찾아서 회전을 시켜줫다면, 이제 B의 top이 A스택으로 옮겨가기만 하면 됩니다.
step7, step8을 b스택이 빌때까지 계속 반복시키면 됩니다.
이렇게 되면 a스택은 정렬이 되어있기는 하지만, 완전히 정렬이 된 상태가 아닐 수 있습니다.
아마 네팔 국기 모양으로 정렬이 되어 있을텐데, 이때는 a스택의 최솟값인 0의 인덱스를 찾아 ra나 rra를 해주시면 됩니다. 이렇게 마지막으로 정렬을 해주게 되면, mandatory는 끝나게 됩니다.
Step. 9 - Bonus
보너스 파트는 checker 만들기 입니다. 앞서 만든 프로그램으로 출력된 명령이 정확한지, 확인하는 것이죠.
checker는 mandatory의 함수들을 이용해서 들어온 인자가 유효한지 판별하고, 들어온 인자가 정렬이 되어있는지 확인합니다.
또한 정상적인 입력이 들어왓다면 명령어를 입력받고 그 입력을 get_next_line함수로 읽어들여 명령어가 제대로 들어왓다면 그 명령을 수행하기만 하면됩니다.
만약 명령이 끝났을 때, 스택b가 비어있고, a는 정렬이 완전히 되어 있다면, ok를 출력하면 됩니다.
이렇게 하면 push_swap 끝~~!!!!
