[42 서울] push_swap을 케이크처럼 쉽게 먹는 법 - 2

서론

어제 평가를 받았다. 역시 글을 쓰기전에 평가를 받으면 평가때 말을 하면서 머리속이 정리되서 글이 더 쉽게 나오는것 같다. 

 

이전 글에도 적혀있지만 코드의 진행은 이 영상과 같다 https://youtu.be/8h7a7NxztkM

 

구현 시작

2개일때와 3개일때의 정렬은 별로 어렵지 않다. 2개일때는 그냥 둘중에 뭐가 더 높은 수인지를 확인해서 sa를 하거나 안하면 되고 3개일때는 경우의 수가 다섯가지이기 때문에 전체를 하드코딩하면 된다.

출처는 https://medium.com/@jamierobertdawson/push-swap-the-least-amount-of-moves-with-two-stacks-d1e76a71789a

이제 3 보다 많은 숫자들을 정렬하기 위해서는 정렬 알고리즘이 필요하다.

 

우선 정렬이 시작되면 모든 수를 3등분 한다.

출처는 https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50

 

출처는 내 영상

위에서 적힌 방법대로 나누면 왼쪽과 같은 모습이 된다. 이걸 이제 전부 스택b로 넘기면 오른쪽같은 사진이 된다.

 

전부 넘긴다고 했지만 실제 코드에서는 3개를 남기고 전부 넘긴다. 남은 세개는 위에 적힌 3개짜리 방법으로 정렬을 한다.

 

여기서 다른 카뎃들과 나의 방법이 달라지는데, 이런식으로 3등분해서 넘기는걸 계속 반복하다가 3개(혹은 5개)가 남을때 정렬을 하고 재귀가 풀리면서 나머지를 같은 방법으로 계속 정렬을 하면 퀵소트로 정렬한 알고리즘이 된다. 

 

나도 처음엔 이런 방법으로 구현을 했었는데 이 방법의 문제는 문자열을 바로 출력하는게 아니고 따로 보관을 해서 최적화를 해줘야한다는 것이다. 그렇지 않으면 인자 100개에서 700개를 넘어서 만점 받기가 어려워진다.

 

그런데 이 방법은 나중에 듣게된 것이고, 구현할 당시에는 방법이 생각이 안나서 그냥 갈아 엎고 그리디 알고리즘으로 다시 구현하였다.

출처는 https://hanamon.kr/알고리즘-탐욕알고리즘-greedy-algorithm/

그리디 알고리즘은 정렬 알고리즘이라고 부르긴 어렵지만, 시간복잡도가 아닌 명령어의 개수만 평가에 반영되는 과제 특성상 만점을 받기에 적합하다.

 

그리디 알고리즘 구현

정렬을 하는 함수의 반복문에서 int형 변수 a와 b를 초기화한다.

 

그다음 가장 적은 명령어 개수로 스택a에 끼워넣을수있는 스택b의 숫자를 찾는다.

 

스택 b에서 숫자를 가지고 와서 그것이 스택 a에 어디에 들어가야하는지 그러려면 스택a 가 몇번 움직여야하는지를 확인한 다음

 

스택 b의 인덱스를 확인한다. 절반을 넘어가면 정방향으로 돌리는거보다 반대 방향으로 돌리는것이 빠르기 때문에 그 부분을 조건문으로 분기해둔다.

 

바깥에서 주소를 가져온 a와 b의 크기를 이번 반복문 안에서 구한 크기와 비교해서 더 작으면 a와 b를 교체해준다.

그 다음에 스택 두개가 같은 방향으로 움직여야 되면 rr이나 rrr을 해서 처리해주고 각각의 스택을 위치에 맞게 조정해준다음 pa를 해준다.

 

이걸 계속 반복하면 이런 모양이 될텐데 이건 이제 '정렬이 됐다' 라고 할수가 없으니 a의 위치에서 가장 작은값이 위로 오도록 함수를 호출해서 해결한다.

이렇게 하면 정렬 끝!

 

마무리와 결론

더 최적화를 할수도 있다. rr이나 rrr을 쓸 상황이라면 하나를 빼고 계산한다거나, 지금 숫자만 위치를 확인하는게 아니고 다음이나 다다음숫자까지 계산을 한다거나... 하지만 어짜피 만점인데 라는 생각이 드니까 갑자기 시간낭비같아서 그냥 제출했다. 극한까지 해봤어도 재밌었을것 같다.

  

평가를 받는 동안 기존에 push_swap을 하신 분들이 되게 신기한 방식이라고 하셔서 기분이 싱숭생숭했다. 유튜브 영상을 보니 해외 카뎃들은 대부분 이런 방식으로 해결하던데, 42서울에서는 기존의 가이드들이 너무 잘 되어있어서 (나도 그랬지만) 그 방식대로 해결하려는 경우가 많은것 같다.

 

하지만 그 가이드들의 퀵소트 정렬은 알고리즘 공부에는 좋지만, 과제를 만점받는건 난이도가 좀 있는 편이었다. 그래서 나도 가이드를 따로 적었다. 이 글을 읽는 카뎃들은 최적화를 깍기위해 고생하는게 아니고 좀 더 쉽게 만점을 받으면 좋겠다. 물론 공부도 잘 되면 더 좋겠지만...