필자가 Amazon PhoneScreen Interview 시에 받았던 Circular Queue (원형 큐, 환형 큐) 구현 문제를 복기해보려고 한다.
기본적인 문제인데, 원리만 자료구조 수업시간에 듣고 실사용도 굳이 구현체의 코드까지 따라가며 복기해본적이 없다보니 어려웠다.
게다가 LP (Leadership Principles)를 영어로 30분하고 나서 머리가 새하얘진 상태로 코딩문제를 풀려니 아무것도 생각나지 않았다.
심지어 폰스크린 인터뷰에서 설계 (Design) 쪽 문제는 안나온다고 많은 블로그에서 봤었는데, 이런 구현 설계는 나오나보다...고 글을 읽으시는 분들은 참고하시면 되겠다.
어쨌든 제대로 못풀었으니 전부 핑계고 변명이다 ㅠㅠ
문제는 아래 링크를 참고하시면 된다.
leetcode.com/problems/design-circular-queue/
Design Circular Queue - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
원형큐를 구현하기 전에 Queue (큐) 에 대해서 좀 더 정확히 알 필요가 있다.
다들 큐는 FIFO (First-In-First-Out, 선입선출) 구조로 이루어진 자료구조임을 잘 알고 있을 것이라고 생각된다.
번호표 시스템이나 스케쥴링 등의 다양한 대기열에 관련된 시스템에서 많이 사용됨도 알고 있을 것이라고 생각된다.
그리고 큐의 Implementation (구현체) 들에 대해서도 알고 있을 것이라고 생각되는데, 필자의 경우에는 스스로는 알고있다고 생각했지만 정확한 쓰임과 차이를 알고 사용했다기 보다는 실전 코딩과 테스트를 통해서 손으로 인지만 하고 있는 상황이었다는 것을 깨달았다. 특히 LinkedList와 ArrayDeque의 차이에 대해서는 정확하게 인지하지 못하고 사용했었다.
광탈 후 자기반성이랄까요...
그래서 인터뷰 중에도 Linked-list 형태의 구현을 시도했었는데, 인터뷰어의 힌트로 주어진 Array (배열) 형태의 구현과 차이를 제대로 인지하지 못해서 더욱 미궁에 빠지는 바람에 결국 풀지를 못했다.
두 구현의 차이를 생각해보면 좋을 것 같다는 피드백도 실제로 받았습니다. ㅠ
원형큐는 큐의 맨 뒤쪽에 도달하게 되면 다시 제일 앞쪽으로 돌아오게 만들면 되는 형태이다.
큐의 Linked-list 형태와 Array 형태의 구현에 대한 상세한 설명 및 원형큐에 대해서는 Stranger's Lab님의 블로그를 참고하시면 되겠다.
여기만큼 자료구조에 대해 잘 설명한 블로그를 못찾았는데 혹시 다른 잘쓴 분들이 있으시다면 댓글로 알려주시길 바랍니다.
필자는 배열 형태의 구현으로 풀어보겠다. Linked-list 형태의 구현은 배열에 비해 조금 쉽고, 다른 블로그에 설명이 잘 되어 있으니 그것을 참고하시는 게 좋을 것 같다. 그 분들 보다 잘 쓸 자신이 없어요ㅠㅠ
전체코드를 복사&붙여넣기 하는 행위는 실력에 전혀 도움되지 않음을 명심하시길 바란다.
class MyCircularQueue {
private int capacity; // Queue의 최대용량
private int size; // 실제 Queue에 담긴 element들의 갯수
private int head; // 현재 head의 위치
private int tail; // 현재 tail의 위치
private int[] elements; // elements 배열 (이 문제에서 int queue를 정의해서 int array 선언)
public MyCircularQueue(int k) { // 생성자
this.capacity = k;
this.size = 0;
this.head = 0;
this.tail = 0;
this.elements = new int[k];
}
public boolean enQueue(int value) {
if (isFull()) { // 만약 Queue가 꽉찬 상태라면 더 이상 넣을 수 없음
return false;
}
elements[tail] = value; // 현재 tail의 위치에 value를 삽입
tail = (tail + 1) % capacity; // tail의 인덱스를 한칸 뒤로 밈
size++; // Queue에 1개 추가되었다는 의미
return true;
}
public boolean deQueue() {
if (isEmpty()) { // 만약 Queue가 빈 상태라면 꺼낼 수 없음
return false;
}
// elements[head] = null; // primitive가 아닐때 loitering 방지
head = (head + 1) % capacity; // head의 인덱스를 한칸 뒤로 밈
size--; // Queue에서 1개 제거되었다는 의미
return true;
}
public int Front() {
if (isEmpty()) { // Queue가 빈 경우에 가져올 것이 없음
return -1; // 문제에서 -1로 명시되어 있음
}
return elements[head % capacity];
}
public int Rear() {
if (isEmpty()) { // Queue가 빈 경우에 가져올 것이 없음
return -1;
}
// tail이 0인 경우 elements[-1]을 탐색하게 되어 오류가 발생하는 것을 방지하기 위함
return elements[(tail + capacity - 1) % capacity];
}
public boolean isEmpty() {
return size == 0; // element들의 실제 갯수를 의미하는 size가 0이면 Queue가 비었다고 할 수 있음
}
public boolean isFull() {
return size == capacity; // size와 선언시의 용량이 동일하다면 꽉 찼다고 할 수 있음
}
}
Leetcode는 매우 친절한 문제풀이 사이트이다. 이렇게 말하는 이유는 Leetcode 내에서는 아래 (더보기 참고) 와 같이 클래스 바디와 메서드들이 주어지는데 실제 인터뷰에서는 그런 일이 거의 없기 때문이다. 아마 테스트를 용이하게 하기 위해서 그런 게 아닌가 싶다.
class MyCircularQueue {
public MyCircularQueue(int k) {
}
public boolean enQueue(int value) {
}
public boolean deQueue() {
}
public int Front() {
}
public int Rear() {
}
public boolean isEmpty() {
}
public boolean isFull() {
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
단순히 Leetcode의 문제를 푸는 것만을 목표로 하는 거라면, 이 글을 더 읽을 이유는 없을 것 같다.
하지만 실제 인터뷰 상황을 준비하는 사람이 있다면, 단순 문제풀이에만 집중하는 경우 (필자처럼) 떨어질 수도 있기 때문에 설계부터 천천히 살펴보도록 하겠다.
우선 클래스의 이름을 지정해야 하는데, 이것은 실행할 파일명과 동일해야 함을 잘 알고 있으리라 생각한다.
그냥 인터뷰때 한마디 더 할 수 있습니다요 -.-ㅋ
클래스를 선언하면 내부에 생성자가 있어야 하는데, 배열은 한번 선언하면 그 크기를 변화시킬 수 없다는 단점이 있기 때문에 배열을 이용한 구현을 할때는 큐에 담을 Capacity (용량) 을 파라미터로 지정한 생성자를 사용한다.
문제 아래쪽에 new MyCircularQueue(k) 를 선언하는 부분을 봐도 k라는 int형 정수를 입력하게 되어 있기 때문에 이 문제만을 풀때에는 고정크기의 배열을 통해 푸는 문제임을 알 수 있다.
덧붙이면, 실제 JDK 내에 구현되어 있는 ArrayDeque이나 PriorityQueue 같은 경우 배열로 구현이 됐지만, 사이즈 변경을 할 수 있게 해두었다. 상세 구현은 ArrayDeque의 doubleCapacity 메서드 또는 PriorityQueue의 grow 메서드를 참고하시길 바라고, 원리는 Stranger's Lab님의 블로그에 또 잘나와있으니 읽어보시길 추천합니다. 이 분 글은 지식도 지식이지만 글이 너무 잘 읽힙니다 ㅎㅎㅎ
만약 인터뷰에서 큐의 사이즈에 대한 내용이 주어지지 않으면, 큐의 사이즈가 고정인지 가변인지에 대해서 질문해야 한다.
저 같은 경우에는 Design Circular Queue 하라고 하고, 메서드 add, remove, isFull, isEmpty에 대해 구현하라고 나왔는데, 큐에 대해서 설명하고 어떤 자료를 담으면 되냐고 물어봤습니다. 인터뷰어는 "Just Integer" 라고 했는데, int로 접근했습니다. -_ㅠ
큐 사이즈에 대해서는 안물어봤는데, 도중에 헷갈려서 어버버하고 있으니 그냥 고정길이로 해도 된다고 했습니다. 그래도 어버버...............
고정길이의 큐를 선언할 것이기 때문에 capacity라는 변수를 선언한다. 이 변수는 생성자의 파라미터로 사용될 것이다.
큐는 앞 (front, head) 으로는 자료를 빼는 역할을 하고, 뒤 (rear, tail) 로는 자료를 넣는 역할을 하기에 head, tail 이라는 변수를 선언해주었다. 이 변수들은 삽입 (enqueue, add, offer) 될때는 tail이 뒤로 가고, 제거 (dequeue, remove, poll) 될때는 head가 뒤로 가는 역할을 한다.
head와 tail의 위치만으로도 큐가 비었는지 (empty), 꽉 찼는지 (full) 알 수 있지만, 좀 더 쉽게하게 알기 위해서 size 라는 변수도 선언해주었다.
생성자의 경우에 Leetcode가 제공하는 것을 보면 public MyCircularQueue(int k) {} 로 되어 있는데, Access Modifier (접근제어자) 를 어떻게 쓸지도 고민해야 한다. 묻지는 않았는데 Leetcode의 다른 인터뷰 수기들을 보면 fundamental 관련해서 질문할때 자주 물어봤다고 한다. 말로 설명하면서 심지어 영어로 코딩을 해야하니 집중이 잘 안되겠지만, 여러번 훈련을 통해 익숙해지도록 노력해야 한다.
네...저한테 하는 말입니다...
생성자 다음에는 큐에 데이터를 삽입하는 메서드를 설계해서 구현하면 된다.
물론 Leetcode의 경우에는 enQueue를 쓰라고 되어 있지만, 인터뷰 상황에서 리턴과 메서드 시그니처들이 주어지지 않는 경우가 많기 때문에 인터뷰이가 설계를 해보는 연습을 해야한다. 라이브 코딩 인터뷰 자체가 단순 코딩 실력을 보는 게 아니라 어떻게 생각(설계)하고 구현(코딩), 그리고 테스트까지 모두 확인하는 과정이다.
필자의 경우에는 실무에서 offer보다는 add를, poll보다는 remove를 익숙하게 썼기 때문에 add와 remove로 구현했었다. (리턴값은 boolean)
생각해보면 삭제하는 경우보다 플래그만 달고 업데이트를 해두는 경우가 더 많았던 것 같기도 하다는 생각이 든다......
코드에 주석을 달아뒀지만 enQueue 메서드부터 설명을 하자면, 현재 head와 tail이 0으로 초기화 된 상황이다.
Capacity가 4 인 큐라고 가정하고 설명하겠다.
그리기 귀찮아서는 절대 아닙니다. 아닙니다.
| 0 | 1 | 2 | 3 |
| head, tail |
여기서 enQueue(10) 을 실행하면 아래와 같이 변경된다.
| 0 | 1 | 2 | 3 |
| 10 | |||
| head | tail |
추가로 enQueue(20) 을 실행하면 아래와 같이 변경된다.
| 0 | 1 | 2 | 3 |
| 10 | 20 | ||
| head | tail |
여기서 deQueue() 를 실행하면 아래와 같이 변경된다.
| 0 | 1 | 2 | 3 |
| 20 | |||
| head | tail |
enQueue(30) 을 실행해보면 아래와 같다.
| 0 | 1 | 2 | 3 |
| 20 | 30 | ||
| head | tail |
이 상황에서 enQueue(40) 을 실행해보면 어떻게 될까?
| 0 | 1 | 2 | 3 |
| 20 | 30 | 40 | |
| tail | head |
고정길이로 선언한 큐의 용량이 4이기 때문에 4번 인덱스로 가는 것이 아니라 0번 인덱스로 가면 된다.
5번째 삽입 (제거 여부와 상관없이) 시도를 하면 4번 인덱스를 사용하려고 할텐데,
해당 인덱스는 존재하지 않으므로 "% capacity" 를 추가해서 마치 직선상의 큐를 원형으로 돌리는 듯한 효과를 준다.
위의 경우에는 deQueue를 한번 발생시켜서 0번 인덱스에 저장이 되었지만, 만약 deQueue를 하지 않아서 용량이 꽉 찬 상태라면 어떻게 될까?
0번 인덱스에 억지로 저장을 하려고 해도 이미 저장되어 있는 값이 있기 때문에 덮어쓰여지게 된다.
이런 경우를 대비하여 enQueue하기 전에 isFull() 메서드를 이용해서 큐가 꽉차있다면 더 이상 삽입할 수 없다 (false) 고 알려주면 된다. 그래서 enQueue 메서드의 처음에 isFull() 메서드가 있는 것이다.
그리고 tail 변수의 경우에 생성자에서 0으로 초기화했기 때문에, 0번 인덱스를 활용하기 위해서 데이터를 먼저 집어넣고 그 다음으로 움직이게 했다.
다른 블로거들은 초기화 값이 0인데도 인덱스 먼저 움직이고 데이터를 넣더라고요. 아니 그렇다고요...
그리고 size 변수를 1 늘려주었다.
deQueue 메서드의 시작에서는 큐가 비었는지를 확인해주면 큐에서 데이터를 안전하게 제거할 수 있을 것이다.
주석으로 써뒀지만, Primitive Type (기본형) 이 아닌 Reference Type (참조형) 인 경우에는 Loitering을 방지하기 위해서 null 처리를 해줘야 한다. 이건 완전 모르고 있었던 내용이긴 한데, 배열로 구현된 ArrayDeque 이나 PriorityQueue 에서는 이미 처리를 해주고 있었다.
간단히 설명하면 고아객체 (다시 참조될 일이 없지만 GC에 수집되지 못하는 객체, 메모리 누수의 잠재 요인) 를 명시적으로 해제해줌으로써 GC에 수집될 수 있게 도와주는 것이라고 생각하시면 되겠다.
기본형 대신 참조형에서만 발생하는 이유는 참조형 배열은 힙에 참조값을 저장하는 공간과 실제 값이 저장되는 공간 두 곳이 할당되기 때문이다.
Loitering 에 대해서는 쉽게 설명된 링크를 찾아 달거나, 없다면 새로 글을 써보겠다. 우선 필자가 처음 해당 개념을 접한 알고리즘 개정 4판 (번역) 로이터링 링크를 참고해서 기본적인 개념을 이해하시면 되겠다. (원서의 경우에는 PDF가 공개되어 있으니 검색해보시길 바란다.)
스택과 힙에 데이터가 어떻게 저장되는지에 대한 자세한 원리는 야붕이님의 블로그의 이 글을 참고하시면 된다. 정말 읽기 편하게 쓰셔서 몇번을 읽었는지 모르겠다. (blog.wanzargen.me/17 이 분의 글도 참고하시면 좋을 것 같다.)
deQueue 메서드 같은 경우에서도 (참조형 배열인 경우에만) 제거를 해준 다음에 head의 인덱스를 하나 밀어준다.
원형큐이므로 "% capacity" 를 추가해줘서 마지막 인덱스의 다음은 처음 인덱스가 될 수 있게 해준다.
큐에서 데이터 하나를 뺐으니 size 변수를 1 줄여준다.
isEmpty() 메서드의 경우에는 size가 0인 경우에도 알 수 있지만, head와 tail의 현재 위치를 통해서도 확인할 수 있다. 대신에 isFull() 을 구현하는 경우에도 head와 tail이 동일한 위치에 존재할 수 있으니, 이 경우를 제외시켜주는 것을 잊지 말아야 할 것이다.
isFull() 메서드의 경우에는 고정길이인 경우일 때만 사용할 수 있다. 이 메서드를 구현하라고 하면 고정길이임을 유추할 수 있겠지만, 인터뷰어에게 꼭 고정길이, 가변길이에 대한 질문을 하기를 바란다.
그 다음으로는 Front와 Rear 메서드인데, 제일 앞이나 뒤의 데이터를 리턴하라는 것이다.
이 메서드들의 구현은 필자의 인터뷰에서는 나오진 않았었지만 만약 해당 메서드들을 구현하라고 했다고 하면, 앞/뒤의 데이터가 동시에 필요한 자료구조는 Deque이니 해당 인터페이스 내의 getFirst(), getLast() 의 형태로 구현을 하겠다.
어쨌든 본인만의 설계를 항상 생각하는 것을 잊지 말기를 바란다.
이 문제에서는 int Front() 를 구현해야 하므로, 우리가 설계한 클래스내에서 앞 (Front) 을 의미하는 head 인덱스가 가르키는 배열의 값을 전달해주면 될 것이다.
다음으로는 int Rear() 를 구현해야하는데, 이 메서드도 Front() 메서드와 마찬가지로 우리가 설계한 변수인 tail 인덱스를 이용해서 풀면 된다. 문제는 tail 인덱스인데, 삽입 (enQueue) 을 수행하고 나서 인덱스를 한 칸 뒤로 미는 작업을 했었다. 그래서 삽입 이후의 tail 인덱스의 위치에는 아무런 값이 없거나, 큐가 꽉 찼다면 Front와 동일한 값을 가지고 있을 것이다. (위의 그림에서 deQueue 시의 tail 인덱스 참고)
그런 상황을 대비해서 Rear() 메서드 내에서는 현재 tail 인덱스의 한 칸 이전의 데이터를 탐색해야 한다. 또 주의해야 할 것은 현재 큐가 비어있는 상태라면 "tail - 1" 처리를 할때 -1 인덱스를 탐색할 수도 있으니 capacity를 더해준다면 어쨌든 % 연산에 의해 완충되는 역할을 할 수 있다.
다른 블로거들의 글을 보면 tail/rear 인덱스를 -1로 초기화하는 경우가 있는데, 이런 경우에 Rear 메서드에서는 tail/rear를 바로 탐색하면 된다는 장점이 있다. 하지만 큐가 비었을때 수행하는 경우에 오류가 발생할수도 있고 배열을 사용하는데에 -1 인덱스를 사용하는 것은 필자의 실무 경험을 비추어보았을때 헷갈릴 수 있으므로 0으로 초기화하였다.
아니면 0으로 초기화 하되, 인덱스를 먼저 밀어둔 다음에 삽입을 하는 경우도 있었다. 이런 경우에는 0번째 인덱스를 처음에 사용하지 못하기 때문에 큐가 한바퀴 돌기전에는 공간낭비가 될 수도 있다고 생각한다.
각 상황에 따라서 다른 구현이 있어야 하니 이 글을 보시는 분들은 어떤 방식으로 구현할지에 대해서 깊이 고민하시고 시뮬레이션 해본 다음에 구현하시길 바란다.
각 메서드들의 Time Complexity (시간복잡도) 와 Space Complexity (공간복잡도) 도 산출해내야한다.
데이터를 추가함에 있어서 딱히 반복문을 통해 탐색을 하는 상황이 없기 때문에 시간복잡도의 경우에는 O(1) 이라고 말할 수 있다.
하지만 큐의 길이가 k로 정해져 있고, 정해져 있지 않더라도 어쨌든 입력되는 N개가 있을 것이기 때문에 공간복잡도는 큐의 길이인 O(k) 라고 말할 수 있다.
인터뷰에서 본인이 구현한 알고리즘의 시간복잡도와 공간복잡도를 인터뷰어에게 알려주는 것 또한 매우 중요한 일이므로 구현을 하면서 소홀해서는 안되는 부분이다.
마지막으로 테스트를 진행해야 하는데, Leetcode가 제공하는 테스트케이스는 보통 빈약한 경우가 너무 많다.
그래서 실제 Submit 을 했을때 Error 가 많이 발생한다. 네, 경험담....맞습니다...ㅎㅎㅎ
설계를 하면서 테스트를 어떻게 해야겠다는 생각을 많이 해야한다. 특히 Edge case를 못찾는 것을 용납하지 않는 구글인터뷰어들이 있다고 하니 조심하시길 바란다.
필자의 Leetcode 테스트케이스는 아래와 같았다.
["MyCircularQueue", "Front", "Rear", "enQueue", "Front", "Rear", "enQueue", "enQueue", "enQueue", "Front", "Rear", "isFull", "Front", "deQueue", "Front", "Rear", "enQueue", "Front", "Rear", "isFull"]
[[3], [], [], [1], [], [], [2], [3], [4], [], [], [], [], [], [], [], [4], [], [], []]
아무래도 인덱스가 왔다갔다 하는 부분이라 비어있을때와 꽉찼을때 Front, Rear를 중점적으로 수행해주면 로직의 헛점을 발견할 수 있을 것이라고 생각했다. 독자분들께서도 꼭 엣지케이스들에 대한 대비도 하시길 바란다.
구글의 폰스크린/온사이트 인터뷰에서는 하나의 코딩테스트에서 Follow-up Question이 많기로 유명한데, 이 문제에서 가능한 질문들을 생각해보면
- 큐의 사이즈를 가변으로 했을때 구현의 차이점은 어떻게 되는지
- 큐에 저장하는 자료형을 제네릭으로 변경 가능한지?
혹시 추가할만한 질문들이 있다면 제보바랍니다.
참고한 문서 및 링크
'Leetcode > medium' 카테고리의 다른 글
| [Leetcode] 970. Powerful Integers (0) | 2021.05.02 |
|---|---|
| [Leetcode] 34. Find First and Last Position of Element in Sorted Array (0) | 2021.05.01 |
| [Leetcode] 63. Unique Paths II (0) | 2021.04.30 |
| [Leetcode] 48. Rotate Image (0) | 2021.04.28 |
| [Leetcode] 1721. Swapping Nodes in a Linked List (0) | 2021.03.19 |
