2022.04.13. push_swap - 스택에 입력값 저장-1, 정렬부 구현

스택에 입력값 저장시, contents는 정상적으로 저장이 되나, arr4i내에서의 index 값이 저장되지 않은 문제점이 있었다.

문제는 line 36줄에 있는 while 문이었다.

현재 arr4 배열의 끝에 문자열 처럼 '\0' 문자를 넣고 배열을 사용 했는데, 문제는 arr4i가 int형 배열이라,

위처럼 input으로 0이 들어오게 되면, 널 값의 ASCII 코드와 동일한 값으로 인식되어, 첫번째로 들어온 input 값인 '3'을 찾기전 i = 1 일때의 arr4i[1]의 값이 0이되므로 while문이 돌지 않게되어 new node에 index를 저장하지 못하게 된것이다.

문자열 처리를 많이 하다보니 int형 배열에 널 터미네이트를 적용해서 생긴 이슈였다.

input amount 값(들어온 input의 갯수)를 make_a_node에 파라미터로 넘겨주고, 문제가 됬던 while 부를 i_amount보다 작을 때 반복되게끔 수정했다.

더불어, main 문에서 arr4i를 메모리 할당하고 터미네이트 하는 부분도 수정했다. (66번 line 메모리 할당 크기 수정, 70번 line 삭제) index_input 함수에서는 arr4i 배열 내의 null terminated 된 것을 이용하는 부분이 없었기 때문에 index_input 함수는 수정하지 않았다.

인풋 값으로 들어온 순서대로 top부터 차례대로 들어간 모습 & 입력값의 크기에 따라 오름차순으로 인덱싱 된 모습

이제 정렬 구현부를 시작할 차례이다.

0. 중간값 보다 작은 값을 스택 b로 옮기기.

1. 스택 a(중간값 이상의 큰 값) 오름차순 정렬

2. 스택b(중간값 미만 값) 내림차순 정렬

3. 둘다 정렬 끝나면 스택 b의 모든 값 pa해서 스택 a로 보내기

 

먼저 더 이상 쓸일이 없다고 판단되는 arr4i를 free 하고, 정렬부를 시작했다.

sort_stacks라는 함수 호출로 정렬을 모두 마치는것을 목표로 한다.

"정렬 명령어 최소 호출"을 목표로 하는 subject 의 목표에 맞게, sort_stacks 내에서 char**형 버퍼를 만들어, 버퍼 내부에 명령어를 저장해 두었다가 합칠 수 있는 명령어는 합쳐서 print 할것이다.

일단 명령어 버퍼을 반환할 수 있게 char **형을 반환으로 해두고, 중간값인 middle 값을 잘 도출 해 내는지 확인해봤다.

middle 값이 잘 출력되는 것을 확인하려고 좀 더 많은 input을 넣어봤는데, 스택 a에 저장된 노드들의 index가 일부 변하지 않은게 확인 되었다.

main 문에서 보니, arr4i 내에 input 값중 몇몇이 비 정상적으로 들어간게 확인되었다.  이로 인해 잘못 저장된 값에 해당되는 contents 들을 arr4i 내에서 찾을 수 없어서, init시에 들어간 index로 들어간게 확인 되었다.

input string 을 atoi로 int형으로 변환해서 arr4i 배열에 저장할 시에는 정상적으로 변환되어 저장되는 것이 확인 되었다. sort4i에서 뭔가 문제가 생긴것인지 확인해 봐야겠다.

sort4i에서 문제가 생긴것이라 판단 하고 확인해 보았으나, 작동 중에 문제가 없었다. arr배열 내에 값이 이상했던 문제는 main문에서 arr 배열을 할당 해제한 이후에 arr4i 배열 내의 값을 출력했기 때문이었다. 여전히 index 값이 일부 node에 제대로 저장되지 않는 문제는 남아있다.

결국, 널 터미네이트를 이용하던 방법에서 들어온 input의 갯수를 사용하는 방법으로 수정하던 중, i가 input 갯수 미만일때까지로 수정했어야 했는데, content의 크기를 비교해 버려서 생긴 일이었다. 공교롭게도 input 갯수보다 컸던 입력값이 44 하나 뿐이라 좀 느리게 알게 되었으나, 미리 테스트하길 잘 한것 같다. 그래도, 앞으로 수정할 때 더욱 신중하게 수정을 해야겠다고 생각 했다. 오히려 처음 코드를 짤 때였다면 하지 않았을 실수를 수정 시에 많이 하게 되는것 같다.

첫 단계인 middle index 보다 작은 값들을 b 스택으로 넘겼다. 그런데, middle은 a스택에 놔두는게 원래 의도였는데, middle도 b로 넘어갔다. 또, index 0의 값도 스택 a에 남아있는 모습이 보였다.

그런데, 스택 b로 우연히 비슷한 값이 넘어갔을 뿐, 함수 작동 구상을 아예 잘못한 것임을 알아챘다. middle 보다 작은 인덱스인지 검사하고, 작다면 b 스택으로 넘겨야한다. 그러므로 비교할 인덱스는 curr->index가 아니라, stack->top_index가 적합하다.(다른 스택으로 넘길때 사용할 수 있는 연산은 pa, pb 밖엔 없고, 해당 연산은 top의 노드에만 작용하므로)

따라서 위와 같이 stack 구조체에 저장되어있는 top_index가 middle 미만이면 pb연산을(do_pstack함수 호출), top_index가 middle 이상이면 ra연산을(do_rstack함수 호출) 해서 중간값보다 작은 값들을 모두 b스택으로 이동시켰다.

 

이제 스택 a는 index 기준으로 오름차순, b스택은 내림 차순으로 정렬할 차례이다.