메모
면접 문제
3.3 접시 무더기
- 접시 무더기를 생각해 보자. 접시를 너무 높이 쌓으면 무너져 내릴 것이다. 따라서 현실에서는 접시를 쌓다가 무더기가 어느 정도 높아지면 새로운 무더기를 만든다. 이것을 흉내 내는 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다(다시 말해, pop()은 정확히 하나의 스택이 있을 때와 동일한 값을 반환해야 한다).
- 힌트
- 각 부분 스택의 크기를 알고 있어야 한다. 스택이 꽉 차면 새로운 스택을 만들어야 한다.
- 특정 부분 스택엑서 원소를 빼낸다는 것은 일부 스택이 꽉 차지 않았다는 것을 의미한다. 이게 문제가 되나? 정답이 있는 것은 아니다. 다만, 이런 경우를 어떻게 처리할지 생각해 보아야 한다.
3.4 스택으로 큐
- 스택 두 개로 큐 하나를 구현한 MyQueue 클래스를 구현하라.
- 힌트
- 큐와 스택의 가장 큰 차이점은 원소의 순서이다. 큐는 오래된 원소부터 삭제하고 스택은 최근 원소부터 삭제한다. 스택의 최근 원소에만 접근이 가능할 때, 스택에서 가장 오래된 원소를 삭제하려면 어떻게 해야 할까?
- 원소가 하나 남을 때까지 스택에서 원소를 반복적으로 빼낸 뒤 임시 스택에 잠시 넣어 두면 가장 오래된 원소를 삭제할 수 있다. 그 다음 최근 원소를 검색한 뒤 모든 원소를 다시 스택에 넣는다. 이 방법의 문제점은 원소를 연속으로 빼내기 위해 O(N) 작업이 매번 필요하다는 점이다. 원소를 연속으로 여러 개 빼내야 하는 이 상황을 최적화할 수 있겠는가?
3.5 스택 정렬
- 가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop, peek, isEmpty의 네 가지 연산을 제공해야 한다.
- 힌트
- 배열을 정렬하는 한 가지 방법은 배열을 순회하면서 모든 원소를 새로운 배열에 정렬된 순서로 삽입하는 것이다. 스택을 사용해서 이 방법을 시도해 볼 수 있겠는가?
- 두 번째 스택이 정렬되어 있다고 생각해 보자. 정렬된 스택에 새로운 원소를 삽입할 수 있는가? 추가 저장공간이 필요할지도 모른다. 추가 저장공간으로 무엇을 할 수 있는가?
- 두번째 스택을 정렬된 상태로 유지하고, 가장 큰 원소를 위에 두라. 첫 번째 스택을 추가 저장공간으로 사용하라.
3.6 동물 보호소
- 먼저 들어온 동물이 먼저 나가는 동물 보호소(animal shelter)가 있다고 하자. 이 보호소는 개와 고양이만 수용한다. 사람들은 보호소에서 가장 오래된 동물부터 입양할 수 있는데, 개와 고양이 중 어떤 동물을 데려갈지 선택할 수 있다. 하지만 특정한 동물을 지정해 데려갈 수는 없다. 이 시스템을 자료구조로 구현하라. 이 자료구조는 enqueue, dequeueAny, dequeueDog, dequeueCat의 연산을 제공해야 한다. 기본적으로 탑재되어 있는 LinkedList 자료구조를 사용해도 좋다.
추가 문제
- 연결리스트(#2.6), 중간 난이도 연습문제(#16.26), 어려운 연습문제 (#17.9)
댓글