[push_swap] 3. 알고리즘 구현 전, 구현 후 반드시 확인해야 하는 사항

말도 안 되는 실수로 거의 일주일을 날려먹고 딥빡쳐서 빠르게 쓰는 글.

 

푸시 스왑을 하고있는 당신, 스택 구현이 끝났다고 싱글벙글 정렬 알고리즘을 구현하러 가기 전 이 사실을 반드시 체크하고 넘어갈 것.

미래의 다른 과제 혹은 프로그래밍을 하고 있을 나, 기본 사항 구현이 끝났다고 싱글벙글 다음 요소를 구현하러 가기 전 반드시 기본 사항에 대해 철저히 검증하고 넘어갈 것.

 

1) 스택의 연산 이후에도 노드 간의 연결이 정상적으로 되어있는지 체크하기.

특히나 이중 연결 리스트로 스택을 구현한 사람들이라면 필히 prev와 next가 정상적으로 연결되어있는지 체크해야한다.

 

그리고 굳이 이중 연결 리스트가 필요할까? 다시 한 번 생각해 보는 것이 좋다...

 

특히나, 특히나 prev를 제대로 연결 안 한다면 당신의 알고리즘은 영문을 모른채 터져나갈 것이다. 왜 터지는지 감이 안오므로 디버깅 하기도 개빡셈.

 

스택의 숫자가 제대로 배열되어 있는 지만 체크할 것이 아니라 스택의 주소값들까지 정상적으로 연결되어있는지 확인해야 한다. top, bottom이 제대로 바뀌어 있는지, 각 노드간 next와 prev가 뒤바뀐 것 없이 제대로 연결되어 있는지, 확인해야 한다.

 

스택의 요소가 한 개일때, 두 개일때, 세 개일때, 네 개일때 까지 다 체크해 보도록. 

 

이중연결리스트 구현따윈 개 껌이라서 체크 안하겠다고? 잊지마라 당신은 어제도 실수했고, 오늘도 실수를 했으며, 내일도 실수를 할 것이다. 나를 믿지 말고 테스트 결과를 믿을 것.

 

2) 각 연산을 출력시키는 함수를 작성할 때 주의하기.

알다시피 ra, rra....등 모든 연산은 실행 될 때 stdout에 해당 연산의 문자열을 출력해야하는데, 실제 연산이 수행되었을 때만 문자열이 출력되어야 한다. 즉, 조건이 맞지 않아 실행이 안 되었다면, 문자열이 출력되어선 안된다. 

 

그딴 실수를 누가하냐고? 그게 바로 나 ㅎ 그리고 아마 당신도...?

 

3) a스택과 b스택을 헷갈리지 않기.

당신의 pb는 a스택의 top을 b스택의 top으로 옮기는 연산이 맞습니까? 

당신의 pa는 b스택의 top을 a스택의 top으로 옮기는 연산이 맞습니까? 

당신의 ra는요? 당신의 rra는요? 당신의....

특히나 지금 tabnine을 사용하고 있다? 깃헙 코파일럿을 사용하고 있다? 그 밖의 자동완성 툴을 사용하고 있다? 축하드립니다! 당신은 스택 연산을 다시 한 번 확인할 기회를 얻으셨습니다. 지금 당장 스택의 연산이 정확한지 다시 한 번 확인하세요.

---

그 외에도 알고리즘을 구현하면서 주의해야 할 점도 있으니 이는 추후에 추가로 작성될 가능성이 농후함.

 

4) 연산을 카운트하는 변수의 증감에 주의하기.

대부분이 퀵소트 알고리즘, 혹은 변형 퀵소트 알고리즘을 이용하여 정렬을 구현할테니...

이 알고리즘을 구현하며 재귀를 위해 사용되는 r값은 pb, ra, 등 연산의 총 count 값이 될 것. 따라서 이 값이 ++되는 기준에 매우 주의해야함. 이 count값이 해당 회차 재귀에서 다른 스택으로 전부 이동되어야 하는 스택의 size와 동일하지 않다면 뭔가 문제가 생긴 것이라 봐도 무방. 때로는 조건이 맞지 않아 연산이 실행되지 않았더라도, 해당 연산의 카운트는 올라가야 할 수도 있다.,,,

 

5) 퀵소트 알고리즘은 원소가 3개일 때, 5개일 때도 정상적으로 동작한다. 비록 비효율적일지라도... 

그말인 즉슨 3개 정렬이 정상적으로 안돌아가면 그 이상의 요소를 정렬하는 것도 정상적으로 안돌아간다는 것... 분명 퀵소트 하라는 대로 구현 했는데 안된다? 그러면 3개부터 돌려보자. 뭐가 문제인지 실마리를 잡을 수 있음.