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

서론

push_swap은 42서울 2서클 과제로 2서클 과제 중 가장 난이도가 높은 것으로 알려져 있다. 책 개구리를 먹어라! 의 교훈대로 2서클에서 가장 어려운 과제를 먼저 잡았다.

 

과제의 내용은 인자의 숫자들을 스택 두 개에 제한된 명령어를 최대한 적게 사용해서 정렬하는 과제이다. 이를 위해 다양한 알고리즘을 공부하고 고민하며 해결 방법을 찾아서 구현해야 한다.

 

이 글은 두 편으로 나눠서 1편에서는 알고리즘 구현 전까지, 2편에서는 알고리즘에 대한 얘기를 할 것이다.

 

다만 처음에 알고리즘을 생각해서 풀었다가 만점을 받기 위한 최적화가 난해해서(인자가 100개일 때 만점이 나오지 않았다), 갈아엎고 과제를 통과하기 위한 코드로 다시 짰다. 그러다 보니 이 글을 보고 구현하면 이 과제에서 학습할 수 있는 내용을 놓칠 수도 있다는 생각이 든다. 

 

따라서 철저하게 학습하고 싶은 분들은 도움이 된 사이트 목록의 minckim's push_swap 가이드를 참조해서 직접 공부하는 게 더 많은 학습이 될 것이다. 이 글은 학습보다는 빠르게 100점 받는 방법에 대해 이야기할 것이다. 케이크는 맛있고 쉽게 먹을 수 있지만 몸에 안 좋으니까...

 

구현한 프로그램을 https://github.com/o-reo/push_swap_visualizer 를 통해 보면 https://youtu.be/8h7a7NxztkM 이 영상과 같다.

 

 

도움이 된 사이트 목록

https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50

push_swap 가이드

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

Push_Swap: The least amount of moves with two stacks

https://epicarts.tistory.com/157

PUSH_SWAP 과제

https://youtu.be/JnbILLTLhOk

https://bigpel66.oopy.io/library/42/inner-circle/7

push_swap

 

서브젝트 정리

정수 값들의 집합을 프로그램에 넣으면 주어진 명령어를 활용하여 스택 두 개를 이용해서 정렬하는 프로그램을 짜는 과제이다.

정렬 알고리즘에서 우리는 복잡도라는 개념을 처음으로 접하게 되는데, 단순히 정렬하는 것은 쉽지만 가능한 한 빠르게 정렬하는 것은 어렵다는 걸 알게 된다.

 

뮬리넷 없이 평가가 종료되며, Libft와 필수 rule이 포함된 Makefile 을 짜야하고, 전역 변수의 사용이 금지되어있으며, write, read, malloc, free, exit 사용 가능.

 

a와 b 라고하는 두 개의 스택으로 구성

a는 중복되지 않는 음수 혹은 양수인 난수들이(인자가) 담김

시작 시 b는 비어있음

 

a의 난수들을 다음과 같은 명령어를 사용해서 오름차순으로 정렬하면 된다.

sa : swap a - 스택 a의 가장 위에 있는 두 원소(혹은 첫 번째 원소와 두 번째 원소)의 위치를 서로 바꾼다.

sb : swap b - 스택 b의 가장 위에 있는 두 원소(혹은 첫 번째 원소와 두 번째 원소)의 위치를 서로 바꾼다.

ss : sa와 sb를 동시에 실행한다.

pa : push a - 스택 b에서 가장 위(탑)에 있는 원소를 가져와서, 스택 a의 맨 위(탑)에 넣는다. 스택 b가 비어 있으면 아무것도 하지 않는다.

pb : push b - 스택 a에서 가장 위(탑)에 있는 원소를 가져와서, 스택 b의 맨 위(탑)에 넣는다. 스택 a가 비어있으면 아무것도 하지 않는다.

ra : rotate a - 스택 a의 모든 원소들을 위로 1 인덱스만큼 올린다. 첫 번째 원소(탑)는 마지막 원소(바텀)가 된다.

rb : rotate b - 스택 b의 모든 원소들을 위로 1 인덱스만큼 올린다. 첫 번째 원소(탑)는 마지막 원소(바텀)가 된다.

rr : ra와 rb를 동시에 실행한다.

rra : reverse rotate a - 스택 a의 모든 원소들을 아래로 1 인덱스만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.

rrb : reverse rotate b - 스택 b의 모든 원소들을 아래로 1 인덱스만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.

rrr : rra와 rrb를 동시에 실행한다.

 

push_swap 이라고 하는 이름의 프로그램을 만들고 인자로 난수를 받는다. 이 프로그램은 a를 정렬하는데 가장 적은 개수의 명령어 리스트를 '\n'으로 구분해서 출력한다.

에러의 경우에는, Error와 줄 바꿈을 표준 에러에 출력해야 한다. 에러는 다음 예시들을 포함한다: 일부 인자가 정수가 아니거나, 정수 범위를 초과하거나, 중복이 있는 경우이다.

 

구조체 만들기

인터넷을 쭉 찾아보니 libft bonus 에서 만든 리스트 함수들을 가지고도 해결할 수 있긴 하던데 이중 연결 리스트로 만든 사람들도 있길래 새로 만들어봤다. 그런데 실제로 코드를 완성하고 보니 prev는 사용하지 않았다. 의식하고 썼으면 더 쉽게 짤 수 있던 부분이 있었을 것 같은데 아쉽다. 어디에 쓸지 생각이 안 난다면 빼는 것도 나쁘지 않다.

 

info 구조체는 스택의 size를 구할 일이 많다 보니 함수의 중복을 막고 라인 수를 줄이기 위해서 그냥 변수에 저장해두기로 했다. 처음에 받은 인자들도 저장을 해뒀는데, 정렬 방식을 갈아엎으면서 쓸 일이 없어졌다.

 

그렇게 만들어진 구조는 다음과 같다.

글씨가 개발새발인건 펜타블렛이 익숙하지 않아서...

처음에 stack_a에 숫자들을 저장해놓고 명령어가 실행되면 다른 구조체와의 관계만 변경하니 메모리 관리하기 쉬워서 마음에 들었다.

 

인자 받아오기

처음엔 별생각 없이 가져오면 된다고 생각했는데 ./push_swap "1 2 3" 4 5 "6" 이런 식으로 다양하게 들어오는 인자를 처리해줘야 한다고 해서 갑자기 골치 아파졌다. 서브젝트나 평가표에 없는 내용을 코딩하는 건 싫지만(그리고 그런 식으로 평가하는 건 부당하다고 생각하지만) 평가에 대비는 해야 해서 ft_split을 이용해서 처리해줬다.

 

가장 먼저 인자의 개수를 구한 다음 그만큼의 메모리를 *num_array에 동적으로 할당해서 그 array를 스택으로 옮겨 담았다. 처음에 잠깐 헷갈렸던 게 서브젝트에도 강조되어있지만 처음 나오는 인자가 맨 앞에 나와야 하는 걸 반대로 처음 나오는 인자가 맨 뒤로 가게 구현했었다. 

 

그래서 array에 인자를 뒤에서부터 채운 다음(size를 알고 있으니까 array[size - index -1] 이렇게) 앞에서부터 넣으려다가 문제가 생겼을 때 디버깅하면서 헷갈릴까 봐 그냥 앞에서부터 차곡차곡 넣었다. 

 

에러 처리

서브젝트에서 요구하는 에러 처리는 다음과 같다.

1. 정수가 아닌 값이 들어왔을 때 'Error' 출력

2. 정수가 중복해서 들어왔을 때 'Error' 출력

3. MAXINT 보다 큰 값 혹은 MININT보다 작은 값이 들어왔을때 'Error' 출력

4. 인자 없이, 혹은 인자가 하나밖에 없거나 이미 정렬된 채로 실행되면 아무것도 출력하지 않고 종료

 

그리고 공백(” “) 들어올 때 프로그램이 터지지 않도록 해야 한다.(체커는 정수가 아닌 값이라고 봐서 Error을 출력하지만 인자가 없는 것으로 봐서 아무것도 출력 안 해도 상관은 없을 것 같다)

우선 print_error이라고 하는 함수를 만들어서 에러시에 exit()을 하되 상황에 따라 "Error\n"을 출력하게 만들어준다.

 

1, 3은 기존 atoi를 가져오면서 살짝만 변형하면 쉽게 구현 가능하고 2, 4번도 묶어서 한 번에 처리할 수 있다.

 

공백(" ")에 대한 처리는 인자를 처리할 때 반드시 처리해줘야 한다. 잘못 만들면 프로그램이 터지기 때문. ./push_swap " " 3 2 이런 건 그냥 정렬을 해줘야 하는 건가 싶었는데 체커에서는 " " 자체가 정수가 아닌 무언가로 처리되는 것 같아서 동일하게 처리했다.

 

명령어 구현

sa, sb, ss = 각 스택의 첫 번째 값과 두 번째 값을 바꾸는 명령어. 설명이 필요 없을 만큼 구현하기 쉽다.  

 

pa, pb = 각 스택의 가장 앞에 있는 값을 다른 스택으로 넘기는 명령어. 두 개의 스택이 서로 값을 주고받는 유일한 명령어이기 때문에 가장 어렵다. 

특히 나는 info 구조체에 워낙 많은 자료를 넣어두다 보니 더 혼란스럽게 코드를 짜게 된 것 같다. 처음엔 대충 만들었다가 에러 날 때마다 계속 몇 줄씩 추가돼서 에러가 더 생기면 이제 노미 넷을 지킬 수 없게 된다고 겁먹었는데 그 정도는 아니었다.

 

ra, rb, rr = 해당 스택의 맨 위 값을 맨 아래로 보내는 명령어. 구조에 따라 다르지만 크게 어렵지 않다.

글을 쓰면서 다시 생각해보니 prev가 없는 게 코드가 훨씬 짧았을 것 같다. 이건 정말 실수인 듯.

 

rra, rrb, rrr = 위와 반대로 해당 스택의 맨 아래 값을 맨 위로 보내는 명령어

명령어들을 쓸 때 예외처리를 꼭 해줘야 하는데, 사실 알고리즘을 잘 만들면 당연히 이 함수가 호출될 일이 없겠지만, 만드는 과정에서는 예외처리가 있는 게 낫다.

 

예외처리를 해두면 잘못된 실행에서 무한루프가 돌던지 해서 쉽게 파악할 수 있고, 지금은 return ; 만 써뒀지만 print_error을 호출하면 명령어에서 문제가 생겼다는 걸 알 수 있다.

 

개발 도중엔 명령어마다 print_error의 인자에 다른 숫자를 넣고 print_error가 실행될 때 해당 숫자와 스택의 내용을 출력하도록 만들어두면 더 쉽게 문제점을 파악할 수 있다. 

 

여기까지 만들었으면 이제 반쯤 왔다. 준비는 다했고 정렬만 구현하면 된다. 나머지는 평가 이후에 쓰겠습니다.