170806(일) - Chapter3 3.6 Sort Stack

Chapter3 3.6 Sort Stack

내 풀이

- SortStack

https://github.com/1dollor/CTCI/blob/master/app/src/main/java/www/breadboy/com/ctci/question3_sort_stack/stack/SortStack.kt

- BinarySearcher

https://github.com/1dollor/CTCI/blob/master/app/src/main/java/www/breadboy/com/ctci/question3_sort_stack/util/BinarySearcher.kt

- 값이 입력될 때마다 여벌스택에 해당 노드가 들어갈 자리까지 매번 빼면 비효율적이다.

· 따라서 들어가야할 자리를 탐색 한 후에 그 인덱스에 해당 노드를 꽂아주는 방식을 사용하기로 했다.

- Stack의 종류에는 Array, LinkedList 가 있다.

· Array : 배열을 쓰게되면 해당 인덱스에 insert 하였을 때, 결국 뒤쪽으로 한칸씩 밀려나므로 좋지 못한 방법이라고 생각했다.

· LinkedList : 위와같은 이유로 LinkedList로 된 스택을 사용하기로 선택.

- 조금 까다로운건 해당 문제에 add 되는 값이 'items' 라고 표현된 점이다. 이렇다면 String, Integer 할거없이 죄다 입력받을 수 있다.

- 탐색방법

· HashMap이 가장 좋은 방식이지만 이건 특정 값을 찾는게 아니라 특정 범위를 찾아야 한다. 그렇다고 매번 인덱스0부터 찾는건 좋지 못하므로 BinarySearch를 조금 변형하여 해당 값이 들어가야할 자리를 찾았다.

- 문제점

· BinarySearch시에 값들의 비교를 CompareTo() 로 하였는데 아무래도 사전적 의미다보니 1과 10중에 10이 더 작다고 판단해버린다.

---

정답

- 매번 여벌 스택에 해당 값이 들어갈 자리까지의 노드들을 옮겨놨다가 다시 push하는 방법 사용.

- 스택 개념을 유지해야 한다면 이 답이 최선이다.

- 조금 이상한건 문자가 입력됐을때의 경우는 생각하지 않는것 같다.

- 매번 처음부터 선형탐색하므로 조금 비효율적이다.