12일차
게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 3.3 ~ 3.6
내용 정리
9 면접 문제
3.3 접시 무더기
접시 무더기를 생각해보자. 접시를 너무 높이 쌓으면 무너져 내릴 것이다. 따라서 현실에서는 접시를 쌓다가 무더기가 어느 정도 높아지면 새로운 무더기를 만든다. 이것을 흉내 내는 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다(다시 말해, pop()은 정확히 하나의 스택이 있을 때와 동일한 값을 반환해야 한다).
답
한 스택의 길이가 일정 이상으로 될 경우, 다른 스택으로 원소를 집어 넣는다. 크기가 꽉찬 스택을 ‘스택들을 보관하는 스택’에 넣는다. 따라서 pop을 할 경우 가장 위에 있는 스택부터 pop이 적용되도록 한다. 빈 스택은 스택을 위한 스택에서 빠진다.
연관문제
특정한 하위 스택에 대해서 pop을 수행하는 popAt(int index) 함수를 구현하라.
답
꽉찬 스택의 길이를 저장하여 해당 index가 어디 스택에 있는지를 확인한 다. 해당 스택에서 모두 꺼낸 후 제거하여 다시 집어 넣는다. 필요하면, 이 스택은 1칸이 새로 생겼기 때문에 이후의 스택들에게서 한개씩 꺼내와야 할 가능성도 있다.
3.4 스택으로 큐
스택 두 개로 큐 하나를 구현한 myQueue 클래스를 구현하라.
답
스택과 큐의 차이는 선입선출과 선입후출의 차이이다. 스택에 들어간 원소를 pop할 때, 나온 원소를 또 다른 스택에 집어 넣는다. 그렇게 하면 기존 스택의 가장 먼저 들어갔던 원소부터 반환할 수 있다.
3.5 스택 정렬
가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop, peek, isEmpty의 네 가지 연산을 제공해야 한다.
나의 답
새로운 스택 하나를 두개를 사용 하여, 그 스택과 기존 스택의 peak으로 본 값을 비교한다. peak으로 본 값이 더 크면, 새로운 스택을 비운 후 이 값부터 넣어줌으로써 가장 작은 값이 항상 위에 오도록 한다. 나머지 하나는 스택의 가장 아래로 넣기 위한 임시 버퍼용 스택으로 사용한다.
정답
스택을 하나만 사용하기 위해선, 정렬된 새로운 스택을 이용한다. 한 스택에서 숫자를 꺼낸 후 임시 변수로 저장하고 정렬된 스택의 넣을 자리를 탐색한다. 그 자리에 가기 까지 만나는 원소들은 꺼내어 기존의 스택에 저장한다. 임시 변수로 저장한 값을 정렬된 스택에 넣어주고, 기존 스택으로 옮겨놨던 스택들을 다시 가져온다. 이 방법을 이용하면 스택을 하나만 더 사용하여 구현할 수 있다.
3.6 동물 보호소
먼저 들어온 동물이 먼저 나가는 동물 보호소(animal shelter)가 있다고 하자. 이 보호소는 개와 고양이만 수용한다. 사람들은 보호소에서 가장 오래된 동물부터 입양할 수 있는데, 개와 고양이 중 어떤 동물을 데려갈지 선택할 수 있다. 하지만 특정한 동물을 지정해 데려갈 수는 없다. 이 시스템을 자료구조로 구현하라. 이 자료구조는 enqueue, dequeueAny, dequeueDog, dequeueCat의 연산을 제공해야 한다. 기본적으로 탑재되어 있는 LinkedList 자료구조를 사용해도 좋다.
답
개와 고양이를 위해 별개의 큐를 사용한다.
읽고 나서
사실 제대로 아는 언어가 파이썬 뿐이라 개념적인 답변을 내놓고 있다. 언어를 배우면 구현하는 법도 배워야 하나..
