[42seoul] Push_swap

굉장히 오랜 시간 블로그 포스팅을 신경쓰지 못했던 나날들을 반성하며
2서클 과제를 다 깬 지금에서야 회고를 해보고자 한다.

Push_swap은 stack A와 B라는 자료 구조를 가지고 A에 입력받은 입력 값에 대해 최소한의 명령으로 stack A를 정렬 하면 되는 과제이다.

이때 stack A와 B가 갖는 기능들을 보았을 때 표현 그대로 자료구조 stack과는 다르고 deque와 유사하다고 보면 된다.

기능 설명

sa, sb, ss : 각 자료구조의 맨 위 두개 요소의 값을 swap
pa, pb : push A (from B), push B (from A)
ra, rb rr : 맨 위 요소를 맨 밑으로 rotate
rra, rrb, rrr : 맨 밑 요소를 맨 위로 rotate

구현 순서

처음 문제를 보고 굉장히 당황했다.
이걸 어디서부터 구현해야할지 몰랐고, 다양한 레퍼런스가 있겠지만 개인적으로 deque 자료 구조를 처음 보았기 때문에 거기서부터 시작했다.

1. deque 구현과 기능 구현

deque는 양방향 큐이다.

앞, 뒤 양쪽 방향에서 요소를 추가하거나 제거할 수 있고 양끝 요소에 접근(ra, rra 등)하여 삽입 또는 제거를 할 경우 배열 혹은 연결 리스트로 구현할 시 이러한 연산에 O(n)이 소요되는 데 반해, 데크는 O(1)로 접근 가능하다.

deque를 C언어에서 norminette 규정과 함수 내 25줄 이내 기준을 지키며 만들기 위해선 각 push, pop (front, back)등을 모듈화하여 하나의 자료구조를 먼저 완성시킨다.

이 이후에 각 기능들에 대해서 순서대로 만들어준다.

pa -> pop_front(b) -> push_front(a)
sa -> pop_front(a) * 2 -> push_front(a) * 2
ra -> pop_front(a) -> push_back(a)
rra -> pop_back(a) -> push_front(a)

이 때 자료구조에 대해 Input의 크기만큼 동적할당을 하기 때문에 과정에서 메모리 누수 혹은 더블 프리 등 메모리 관련 문제를 주의하여 작성하여야 한다.

2. 입력 값 분류하기

deque 자료구조가 구현되었다면, 입력 값에 대한 유효성을 검사해야한다.
subject에서 checker_Mac이라는 프로그램을 주는데 ./checker_Mac Inputs 형태로 입력 시 OK!가 뜬다면 유효한지 확인해볼 수 있다.

모든 경우를 확인해볼 수 없지만 짧게나마 내가 테스트해보고 구현할 때 예외적이거나 까다롭다고 생각했던 케이스들은

./push_swap "0 1 4" 3 5 "      8 9" //argc => 5
./push_swap "         -1 1 0" //argc => 2
./push_swap //argc => 1

솔직히 구현한지 시간이 지나서 모든 케이스가 기억이 나지 않지만 맨 처음 케이스를 구현하려니 막막했어서 기억이 난다.

특히 문자열을 정적으로 선언하는 sizeof(argv[2])와 같은 방법을 사용할 수 없으니 이 부분에서 특히 메모리 누수를 주의하며 동적 할당으로 파싱해야한다.

argv => 1 (해줄 수 있는 것이 없다. 종료 코드 0)
argv => 2 && sorted => (해줄 수 있는 것이 없다. 종료 코드 0)
argv => 2 (문자열 공백 기준으로 파싱 후 숫자인지 체크 후 정렬 체크)
argv => 3 이상 => 각 문자열에 argv => 2 과정을 반복

이렇게 분류하여 파싱이 완료되었다면 모두 stack A에 넣어주면 이제 정렬을 하기 위한 준비가 완료되었다.

3. 정렬 알고리즘 선택

Push_swap을 해결하기 위해서 사용할 수 있는 알고리즘은 많다.

대표적으로 퀵 정렬, 모래시계 알고리즘, 그리디 알고리즘 등이 있다.

이 중에서 나는 그리디 알고리즘을 선택했는데 이유는 다음과 같다.

1. subject의 목표는 최소한의 명령어이기에 시간 복잡도 혹은 연산 횟수를 신경쓸 필요가 없다.
2. 구현이 완성된다면 subject의 목표를 (거의) 무조건적으로 완료하기에 최적화에 시간을 쓸 필요가 없다.

4. 정렬 알고리즘 구현

그리디 알고리즘은 사실 42 내부에서 push_swap을 구현할 때 가장 대중적으로 사용하는 방법이라 팔만코딩경에 이론적으로 잘 정리된 문서가 아주 많기 때문에 참고할 수 있었다.

1. stack A에 있는 모든 값을 먼저 인덱싱해준다.
   인덱싱을 해주는 이유는 값과 값 사이에 들어갈 위치를 찾음에 있어 가장 최소한의 명령어를 찾기 때문에 단순한 값 비교를 통해 해당 값이 어떤 숫자의 사이에 있는지 찾게하기 위함이다.
   (물론 사용하지 않고 구현할 수도 있겠지만 나는 이 방법이 제일 편하다고 생각했다.)
2. stack B에 A에 있는 값을 옮긴다.
   최대 인덱스를 기준으로 pivot을 2개 잡는다.(1/3 지점, 2/3 지점) 3/3 지점을 제외한 1/3 지점과 2/3 지점에 속하는 요소들을 stack B에 옮겨준다.
   이 때, 1/3 지점은 stack B에 push와 동시에 rb를 통해 밑으로 내려준다.

위 과정이 완료되었다면 stack A에는 3/3지점, B의 상단에는 2/3지점, 하단에는 1/3 지점으로 3분할이 완료되었을 것이다.

3. stack A에 있는 3/3 지점을 정렬하지 않고 A에 3개의 요소가 남을 때까지 B에 push한다.
4. stack A에 있는 3개 요소에 대해 하드 코딩으로 정렬을 해준다.
5. stack B의 맨 위 요소부터 A에 들어가기 위해 A에 대해 몇번의 명령어가 필요한지 (정렬된 상태에서 인덱스의 사이값인 A의 요소가 A의 front 위치에 오기 위해) 체크하는 부분을 구현한다.
   이 때 B에 있는 모든 요소를 돌며 A에 들어가기에 가장 적은 명령어가 소모되는 요소를 찾는다.
   B 같은 경우 맨 위부터 하나씩 밑으로 내려가기 때문에 전부 체크할 때 count와 같은 변수를 선언해서 하나씩 증가시키면 곧 그게 sb를 사용하는 양이기 때문에 B에서 몇 번의 명령이 필요한지 찾는 것은 아주 쉽다.

주의사항이 있다면 A의 현재 크기의 절반을 넘었다면 ra보다는 rra를 사용하는 것이, B의 경우도 rrb를 사용하는 것이 효율적이기 때문에 절반이 넘는 경우 count - size와 같이 마이너스로 구분해서 명령어 횟수를 세는 것이 명령어 수를 줄일 수 있다.

6. 최소 명령만큼 A와 B를 회전시킨 후 A에 B의 요소를 push
7. B의 모든 요소가 A로 넘어갈 때까지 5~6의 과정 반복
8. 마지막으로 index가 최소인 요소가 A의 맨 위로 올 수 있도록 A를 회전하면 끝 !