개발 순서
- 매개변수 파싱
- 예외처리
- 연결 리스트로 변환
- push_swap 커맨드 구현
- 정렬 알고리즘 적용
매개변수 파싱 및 예외처리
- 정수 형태의 배열을 할당할 크기 계산
- 모든 매개 변수들을 공백을 기준으로 이어붙이기
- 공백을 기준으로 매개변수 나누기
- 생성된 문자열의 배열을 정수값을 가지는 연결 리스트로 변환하기
메인 함수에서 매개변수를 입력받는데 이때, 1 2 3의 형태 뿐만 아닌 "4 5 6"의 형태로도 입력을 받을 수 있다. 1 "2 3 4" 5 "6"과 같은 복합적인 형태로도 입력받을 가능성이 있기 때문에 매개변수를 파싱하는데 약간의 까다로움이 있었다.
따라서 모든 매개변수를 공백을 사이에 두고 하나의 문자열로 이어붙여준 다음 split 함수를 통해 배열로 분리시켜주었다. 그리고나서 atoi함수를 응용시켜 정수로 변환해주면서 연결 리스트로 할당해주었다.
ex) 1 2 3 " 4 5 6 7" 8 "9" //join 함수 활용
-> "1 2 3 4 5 6 7 8 9" // split 함수 활용
-> {"1", "2", "3", "4", "5", "6", "7", "8", "9"} // atoi 함수 응용여기서 올바른 숫자의 형태가 아니거나 정수의 범위를 초과했을 경우, 그리고 중복되는 수가 존재할 경우 Error처리를 해주었다.
정렬 알고리즘 구현
해당 과제를 구현하기 위한 정렬 알고리즘으로 퀵 정렬, 합병 정렬, 모래시계 정렬 등이 주로 사용되었다고 한다.
나 또한 위의 알고리즘 중에 고민하였고, 그 결과 합병 정렬을 적용시키기로 결심했다.
세 알고리즘 중에 가장 push_swap에 활용되지 않았을 것 같은 알고리즘이기도 했고, 무엇보다 최악의 경우에도 안정적인 커맨드 횟수를 유지할 수 있을 것이라 판단했기 때문이다.
합병 정렬을 적용시키는 아이디어는 "팔만코딩경 - Push Swap 병합 정렬로 해결하기" 를 참고하였다.
내가 머리가 나빴는지 퀵 정렬과 모래시계 정렬에 비해 합병 정렬은 이해하는 것이 매우 어려웠다.
삼각형 여러개로 분할한 뒤 병합하라는 것이 아무리 읽고 이해하려 해봐도 도무지 이해가 가지 않았다.
정렬된 형태(위 삼각형)을 만들기 위해서 아래삼각형 아래삼각형 위삼각형의 형태를 만들어야 한다는게 무슨 의미인지 몰라 무작정 삼각형을 만들어보았다.
10개의 랜덤한 수를 정렬해보기로 했다. 3개의 삼각형을 만들기 위해 10을 3등분 하였고, 나머지는 가운데 삼각형에 배치하여 3 4 3의 형태를 만든다. 이 때, 사이즈 3~4의 삼각형 모양을 보장하기 위해 매 시도마다 첫번째, 두번째, 마지막 숫자를 비교하여 가장 큰 수를 B스택에 담는다.
위의 사진과 같은 경우는 10이 가장 크기 때문에 sa, pb 명령을 시도한다.
이번엔 9가 가장 크기 때문에 rra, pb 명령을 시도한다. 이렇게 3번 pb를 하게 되면 이제 아래를 향한 삼각형 2개를 만들어준다.
이렇게 삼각형 3개가 완성이 됐다. 다음은 병합을 위한 준비 단계로 하나의 삼각형을 stack A로 다시 push해준다.
그 다음 stack A의 bottom, stack B의 top, bottom 중에 최대값을 stack A의 top에 쌓아준다.
이런식으로 3개를 비교해가며 push 과정을 반복해준다.
이런식으로 정렬이 되는 모습을 확인할 수 있었다. 그리고 stack B의 숫자가 2개만 남았을 때에는 둘 중 비교하여 큰 수부터 push를 해주면 정렬할 수 있었다.
조금은 무식하지만 직접 삼각형을 그려봄으로써 해당 알고리즘에 대해 조금이나마 이해할 수 있었다.
일단 여기까지 코드로 구현을 해봐야겠다
숫자 10개가 있을 때에는 정렬이 되었다. 근데 스택 B가 비어있어야하는데 뭔가 커맨드 함수에서 리스트 부분을 잘못 설정한 것 같다.
그리고 더 많은 숫자가 들어갔을 땐 정렬이 되다 만 느낌이다. 아무래도 10개의 정도의 숫자가 삼각형 3개로 나누어 정렬하기엔 가장 최적인 것 같고, 그 보다 더 많은 수들은 팔만코딩경에서 참고한 내용처럼 삼각형을 더 잘게 쪼개야할 것 같다. 아무래도 재귀호출을 적용시켜여할 것 같다.
재귀 호출 적용
이번 과제에서 재귀 호출이 꽤 많이 사용 되었다. 삼각형 모양이 3~5가 될 때까지 재귀호출을 통해 분할시키긴 하는데 한가지 간과한 것이 있었다.
처음엔 34개의 숫자를 3개로 나누면 11 / 12 / 11이 되는데 이것을 한번 더 나누어 3 5 3 / 4 4 4 / 3 5 3 으로 나누었었는데, 이렇게 하면 나중에 삼각형을 하나로 병합할 때 같은 세트의 삼각형끼리 병합하는 것이 아닌 서로 무관한 삼각형끼리 병합을 하게 된다.
따라서 재귀 호출을 통해 해당 숫자에 따른 분할해야하는 삼각형의 크기를 배열로 만들어 주었다.
34 = 11, 12, 11
11 = 3, 5, 3 / 12 = 4, 4, 4 / 11 = 3, 5, 3
각 각의 첫번째 숫자들을 0~2번 인덱스에 배치하고, 두번째 인덱스를 3~5번 인덱스에, 마지막 숫자를 6~8번 인덱스에 배치한다.
[3, 4, 3, 5, 4, 5, 3, 4, 3]이런 식으로 분할해야할 삼각형의 크기를 만들어 주고, 이번엔 재귀호출을 사용하여 삼각형의 방향을 담은 배열을 만들어준다.
34는 3으로 2번 나눠야 6보다 작아지기 떄문에 2번만 재귀 호출을 한다. 윗방향을 1, 아랫방향을 0으로 둔다면
1 = 1, 0, 0
> 1 = 1, 0, 0
> 0 = 1, 1, 0
> 0 = 1, 1, 0
이 되므로 [1, 0, 0, 1, 1, 0, 1, 1, 0]을 담은 배열을 만들 수 있다.
배열의 크기만큼 반복하여 두 배열의 요소를 활용하면, 반복할 때마다 삼각형의 크기와 방향을 구할 수 있다.
모든 숫자들을 분할하고 나면 병합을 진행할 차례이다.
34 같은 경우는 좌측으로 한번, 우측으로 한번 총 2번의 병합을 거치면 된다.
물론 그냥 병합하는 것이 아닌 분할하기 이전의 삼각형들 끼리 병합을 진행한다.
예를 들어 34는 11로, 11은 3, 5, 3으로 나누어졌으니 3, 5, 3끼리 병합하여 11의 삼각형을 만들면 된다.
그 다음엔 11, 12, 11의 삼각형끼리 병합하게 되면 정렬된 모습을 확인할 수 있다.
6개 이하의 정렬은 따로 처리해줘야 한다.
bonus
gnl을 통해 커맨드를 입력받고 숫자가 정렬되었는지 확인해주는 프로그램을 만들면 된다.
첫 평가를 받았는데 mandantory는 무난히 100점으로 끝났지만 보너스에서 요구하는 부분을 하나 처리해주지 못했다.
해당 명령어가 아닌 명령어를 입력받았을 때 Error처리를 해줬어야 했다.
