파싱 추가 사항

hyunlee님이 추가로 처리해야 하는 부분을 알려주셨다.
이런 건 왜 끝도 없이 나오는지 모르겠다.

만약 ./push_swap "1 3 5" 이렇게 들어온다면, 1 3 5 가 하나의 문자열로 들어온다. 이걸 1 , 3 , 5 로 쪼개야 한다.
우리에겐 ft_split()이 있으니 그걸 사용하기로 했다.

많이 바꿔야 하나 싶어서 걱정했는데 많이 바꿀 필요는 없었다.
main()에 들어온 인자(문자열) 하나씩 확인하면서 그 인자를 또 ft_split()으로 나눈 이중배열을 만들었다.
예를 들어, ./push_swap "4 2" 42 이렇게 들어오면 첫 번째 문자열 argv[1](=4 2)를 확인한다.
이 문자열을 다시 ft_split(argv[1], ' ')로 잘라서 char *형의 arg에 담아준다.
이제 arg[0] = 4, arg[1] = 2가 되었다.
그럼 다시 반복문을 돌려서 arg의 0번째부터 끝까지 노드를 하나씩 만들고 값을 담아준다.

뭐랄까 이전에 main()에서 받아온 인자 argv를 가지고 반복문 돌려서 했던 작업을 ft_split()으로 만든 이중배열 arg로 돌리는 반복문 안에 넣어줬다. 그 정도 차이?
여기서 ft_split()으로 받아온 이중배열 잘 free() 해주기!

---

알고리즘 공부

어떤 알고리즘을 사용할 것인지 고민했다.

방법 1

가장 먼저 ji-kim님에게 설명을 들었다. 쏙쏙 이해가 가게 잘 설명해주셨다. 💙

기본 원리

1. 먼저 Quick Sort로 정렬한다. (임시로 정렬하는 것. 어차피 기능을 동작시키는 횟수가 적어야 하는 것이지, 프로그램 자체가 빨라야 하는 것은 아님.)

2. 적절한 피봇을 2개 설정한다. 작은 값을 피봇 1, 큰 값을 피봇 2 라고 칭하겠다. (아마 정렬한 상태에서 크기를 비교해서 최소값과 중간값 사이의 피봇 하나, 최대값과 중간값 사이의 피봇 하나를 설정하기 위함인 것 같음.)

3. 먼저 스택 b에 피봇 1 보다 작은 값을 pb한다.

4. 그 다음으로 스택 b에 피봇 1 보다는 크고 피봇 2 보다는 작은 값을 pb한다.

5. 스택 b에서 가장 큰 값과 두 번째로 큰 값을 찾는다. 가장 큰 값을 max, 두 번째로 큰 값을 max' 라고 칭하겠다.

6. max 와 max' 를 pa하기까지 rb를 몇 번 해야 하는지 횟수를 센다.

7. max 의 횟수와 max' 의 횟수에 1을 더한 값을 비교해서 더 빨리 할 수 있는 것을 먼저 rb하고 pa한다. (max' 을 먼저 보내면 sa를 해야 하기 때문.)

8. 여기에 추가로 최소값 min 을 설정해서 사용할 수도 있다. max 와 max' 과 min 까지 비교한다. min 은 pa하기까지 rrb를 몇 번 해야 하는지 횟수를 센다. 그리고 pa를 한 후에 ra를 해야 하기 때문에 역시 rrb 횟수에 1을 더해서 비교한다.

방법 2

minckim님의 push_swap 가이드
(minckim님께 허락을 받고 올립니다. 좋은 말씀과 함께 친절하게 답변해주신 minckim님께 무한한 감사를 드립니다. 🙇🏻‍♀️🙏🏻)
minckim님께서 슬랙에 공유해주신 노션을 보고 공부했다.
아직 코드는 안 짰는데 일단 내가 보고 이해한 내용을 적어보겠다.

기본 원리

이 방법은 적절한 피봇을 2개 선택하고, 두 피봇 중 큰 피봇보다 크거나 같은 값을 가진 노드는 ra를 통해 스택 a의 맨 밑으로 보낸다.
그리고 큰 피봇보다 작은 값을 가진 노드는 pb를 통해 스택 b로 보낸다.
여기서 작은 피봇보다 작은 값을 가진 노드는 rb를 통해 스택 b의 맨 밑으로 보낸다.
이렇게 하면, 스택 a에는 큰 값들이 분포하게 되고, 스택 b에는 그보다 작은 값들이 분포하게 된다.
그런데 여기서 또 다시 스택 b에서 위쪽에는 비교적 큰 값들이 분포하게 되고, 아래쪽에는 비교적 작은 값들이 분포하게 된다.

일단 기본 원리를 이해하는 건 어렵지 않았다. 그냥 숫자 10개 정도로 직접 해보면 된다.
문제는 저 기본 원리로만 하다가 '근데 정렬은 어떻게 해? 정렬은 안 되는데?' 이러고 있었다는 것... 🤦🏻‍♀️

실제로 사용하는 방법

일단 실제로 사용할 방법은 위에 작성한 것과 살짝 다른 부분이 있기도 하고 추가해야 할 부분도 있다.

(두 피봇 중 큰 피봇을 피봇 1, 작은 피봇을 피봇 2 라고 칭하겠다.)
살짝 다른 부분은, 위에서는 스택 b에 옮겨진 값들 중 피봇 2 보다 작은 값을 가진 노드를 rb 했는데, 이번에는 피봇 1 보다는 작고 피봇 2 보다는 크거나 같은 값을 가진 노드를 rb 한다는 것이다.
그리고 마지막에 ra와rb가 겹치는 경우만큼 rrr을 해서 다시 돌려주고, 남는 경우는 따로 처리한다.(ra가 남으면 그 남은 횟수만큼 ra를 한다.)

a_to_b

1. 스택 a에서 적절한 피봇 2개를 선택한다.

2. n 개의 원소에 대해(n 은 나중에 함수를 조합할 때 재귀로 호출하는 과정에서 인자로 들어옴) 다음 3번과 4번을 반복한다.

3. 스택 a의 top이 피봇 1 보다 크거나 같으면 ra해서 스택 a의 밑으로 보낸다. 그리고 ra의 횟수에 1을 더한다.

4. 스택 a의 top이 피봇 1 보다 작으면 pb해서 스택 b로 보낸다. 그리고 pb의 횟수에 1을 더한다.
   4-1. 스택 b의 top이 피봇 2 보다 크거나 같으면 rb해서 스택 b의 밑으로 보낸다. 그리고 rb의 횟수에 1을 더한다.

5. 위의 반복문이 끝나면, ra와 rb의 호출 횟수가 겹치는 만큼 rrr을 해서 다시 돌려주고, 남는 경우는 따로 처리한다.(ra가 남으면 그 남은 횟수만큼 ra를 한다.)

b_to_a

1. 스택 b에서 적절한 피봇 2개를 선택한다.

2. n 개의 원소에 대해(n 은 나중에 함수를 조합할 때 재귀로 호출하는 과정에서 인자로 들어옴) 다음 3번과 4번을 반복한다.

3. 스택 b의 top이 피봇 2 보다 작으면 rb해서 스택 b의 밑으로 보낸다. 그리고 rb의 횟수에 1을 더한다.

4. 스택 b의 top이 피봇 2 보다 크거나 같으면 pa해서 스택 a로 보낸다. 그리고 pa의 횟수에 1을 더한다.
   4-1. 스택 a의 top이 피봇 1 보다 작으면 ra해서 스택 a의 밑으로 보낸다. 그리고 ra의 횟수에 1을 더한다.

5. 위의 반복문이 끝나면, ra와 rb의 호출 횟수가 겹치는 만큼 rrr을 해서 다시 돌려주고, 남는 경우는 따로 처리한다.(ra가 남으면 그 남은 횟수만큼 ra를 한다.)

이제 함수를 적절히 조합해서 재귀를 이용해 정렬해야 한다.

스택 a를 계속 덜어내다가 정렬이 되면 그때 스택 b에서 덜어냈던 만큼 다시 스택 a로 가져오고, 다시 정렬하고 다시 가져오고,,, 반복반복
여기서 덜어낸 만큼 을 구하려고 기능을 동작시킨 횟수를 센 것이다.

더 자세한 내용은 다음 글에서 마저 작성하겠다.

---

마무리

어휴 데이식스가 끝나질 않아.. 데이식스...? 😮 내일 코딩요는 데식이닷 🎸🎵
하튼 하루가 하루가 아니라서.. 며칠 동안 공부한 양을 하루에 올리는 게 양심 따위 없습니다.

근데 또 블로그를 쓰니까 확실히 과제를 더 빨리 하지는 못해서 뭔가 아쉽기도 하지만 이렇게 꾸준하게 쓰는 게 처음이라 뿌듯하기도 하다. 헷 (*/ω＼*)

hyunlee님이랑 저 알고리즘 원리에 대해 얘기하다가 오아시스 화이트보드에 막 쓰면서 해봤는데 그렇게 하니까 이해가 쏘옥 됐다.
그래서 그때 그렸던 것을 블로그에 깔끔하게 올려보고 싶다. 도전~!

내일은 코드 짜야지.