2서클 과제중 가장 어렵다는 push_swap을 Greedy로 해결한 이야기에 대해 기제하고자 합니다.
서론
작성하는 이유는
- push_swap을 그리디로 풀이한 글이 별로 없어서
- 내 코드 자랑할라고
- 블랙홀 빠지기 전, 42글 하나는 올리려고,,,
처음에는 그냥 머지소트로 작업하려 했으나,, 100점이 안 나온다더라고요?
다른분들은 거의 투 피벗 퀵소트나 모래시계 알고리즘을 사용하셨습니다.
다 하는거 싫어서 주위에 여쭈어봤더니 "그리디"로 하신분이 계셨습니다.
저의 푸시스왑 선생님의 설명을 참고해서 해결하게 되었습니다.
그리디
Greedy 알고리즘은 "순간순간 최적의 선택"을 합니다.
매 순간 최적의 경우를 선택하기 때문에 그 과정 자체가 최적화입니다.
다른 알고리즘을 이용한 경우, 명령어들을 모두 다른 리스트에 담았다가 최적화를 시켜주시던데. 그리디는 그럴 필요 없습니다. 개쩔조?
로직
목차만 작성해보고 뒤에 천천히 설명해볼게요.
- argv 읽어서 deque에 init 하고, 정렬된 배열하나 만들어서 data를 인덱스로 교체
- 스택 a에 원소 3개가 남을때까지 b에 push하고, 스택 a 정렬하기 (3개 하드코딩)
- Greedy 시작. 스택 b가 빌 때 까지 스택 b의 모든 원소들이 스택a의 올바른 위치에 이동할 때,필요하 ㄴ연산 횟수를 모두 계산하여 가장 작은 값을 가진 원소 하나만 b에서 a로 push
- 스택 b가 비었으면, 스택 a에서 0을 찾아서 0이 front가 되도록 만들어 줌
끝 입니다. 간단하지요?
0. 구조 & 명령어
양방향 연결리스트로 구현하였습니다. 그래서 이름도 deque 입니다.
구조체는 이렇게 2개 썼어요.
deque의 이름에 맞게 명령어들을 구현에 주었습니다.
서브젝트에 제시된 명령어에 deque command를 그대로 사용했습니다.
1. 파싱
이 부분은 개인이 구현하기 나름이라고 생각합니다. 저는 이렇게 했다..
- argv 읽어서 스택 a에 push_back
- 동시에 int 형 arr배열에 저장
- arr배열 정렬해서 스택 a의 data값을 정렬된 배열의 인덱스로 교체
제 핵심은 "인덱스 값으로 교체"하는 것 입니다.
이렇게 해도 됨?
ㅇㅇ 이 서브젝트는 들어온 인자를 정렬하는 "명령어를 출력"하는게 목표이기 때문에, 들어온 인자를 재사용하지 않음!!
인자가 ./push_swap 5 9 7 2 1
이렇게 들어왔다면
이제 2 4 3 1 0 으로 바꾸어주는 것.
이렇게 하면 뭐가 좋은가요!
- 마지막에 정렬 할 때 가장 작은 값은 무조건 0이라서 편함
- 분할 파트에서 보면 pivot 정할때 편함
이 부분을 평가에서 칭찬받아서 기분이 좋았어요
2. 분할
다른 분들이 투 피벗 퀵소트를 많이 하신다고들 하시던데, 그 부분을 참고하여 분할합니다.
저의 선생님께서 참고하신 글이 https://techdebt.tistory.com/26 이 글 이라고 하셨어요.
어.. 저의 두번째 선생님입니다. 도움을 많이 받았습니다.
어,, 근데 제가 설명하려는 말들이 다 여기에 있네요.
- pivot 2개를 설정해서 3분할
- 스택 a에는 pivot2보다 큰 원소만 남아있음.
- 스택 a에 3개만 남겨놓고 전부 b로 push
- 스택 a에 남은 3개 하드코딩
까지가 그리디 직전까지의 준비입니다.
여기서 왜 3분할을 해준후에 다 넘겨주나면, 3분할 해서 큰 집합의 순서대로 정렬하기 위함입니다. 이 부분은 직접 실행해보시거나, 두번째 선생님의 유튜브를 보시면 알 수 있습니다.
분할을 해주는 과정이 이후에 정렬을 하게 될 때, rb와 rrb를 적게 해주는 요인이 됩니다.
3. 그리디
전체적인 정리는,,
스택 b가 빌때까지 반복 b->a로 이동할 때, 가장 적은 명령을 이용하는 원소를 찾아서 push해주는 것
이 때 중요한게, a는 0이 가장 위가 아닐 뿐, 항상 정렬된 상태여야합니다.
그래서 우리는 b에서 a로 push 할 때, 앞 원소보다 크고 뒷 원소보다는 작은 위치에 정확히 push 할거에요.
예시를 들자면
a : 13 20 4 10 12
a스택이 이렇다고 합시다. 지금 4가 중간에 있지만, 4 10 13 15 20 순으로 정렬되어있죠?
b : 14 7
여기서 경우를 따져볼게요.
- 14를 push하는 경우
a : 20 4 10 12 13
b : 14 7
이 상태로 만들어서 push를 해야겠죠
a : 14 20 4 10 12 13
b : 7
이 상태가 됩니다.
a에서는 ra1번, b에서 0번, 총 명령어 사용 횟수 1번입니다.
- 7을 push 하는 경우
a : 10 12 13 20 4
b : 7 14
이 상태로 만들어서 push를 해주면
a : 7 10 12 13 20 4
b : 14
이 상태가 되는거고, a에서는 rra 2번, b에서 ra 1번 총 명령어 사용 횟수 3번입니다.
그렇다면 14를 push할때가 7을 push할 때 보다 1번 < 3번으로 더 적어서, 14를 push 하게 됩니다.
이 과정을 스택 b가 빌 때 까지 계속 반복.
상세 함수들에 대해 설명을 해볼게요.
find_best
스택b의 front부터 back까지, 이 원소가 a로 이동하려면 명령어를 얼마나 써야하는지 계산함.
이거 할 때, 스택사이즈 반을 넘어가면 rb하는 것 보다 rrb하는게 더 이득이잖아요. 그래서 그 부분은 이제 + 랑 - 로 분류를 해주었습니다.
스택 b에 있는 원소가 스택 a에 들어갈 때, 알맞은 자리를 찾는 함수입니다.
뭐,, 상당히 더럽고 마음에 안들어요. 그치만 이 부분에 대한 코드를 찾기가 어려워서 제 더러운 코드를 올립니다.
제가 front->prev=NULL, back->next=NULL로 설정했기 때문에, NULL을 역참조 하지 않도록하다보니 더러워졌습니다.
어쩔수 없었어요 블랙홀 1열이었다구요
before_push 어쩌고
push 상태로 스택a랑 스택b를 변경
스택 a와 b를 같은 방향으로 동시에 돌려주는게 _all
각각 돌려주는건 _single
last_sort
스택b는 비어있고, 스택a는 정렬된 상태이지만, 0이 중간 어딘가에 있을거임. 0이 가장 상단에 위치하도록 rotate함.
정리 및 회고
100개 5점 기준 700개 통과!
500개 5점 기준 5500개 통과!
뿌듯한 사람입니다.
그치만 시간이 촉박했던만큼, 더 가독성 좋고, 줄일만한거 더 줄인 코드를 포기했음이 아쉽습니다.
푸시스왑 선생님 승훈님과 푸시스왑을 케이크처럼 퍼먹는 방법을 올려주신.. 선생님의 인트라 네임을 알고싶어요 감사합니다!!!
그리고 새벽에 같이 에러 잡아주신 조주님이랑 첫 평가자로 와주셔서 많은 것을 가르쳐주고 칭찬해주신 썬박님 감사합니다
근데 이렇게 냅다 이름 적어도 괜찮은건가요? 감사하다고 말 하기 부끄러우니까 허공에 외치는거죠 ㅇㅇ
푸시스왑 끗
