Leetcode 75에는 꽤 다양한 패턴의 문제들이 골고루 수록되어 있다. 그래서 아직 패턴 별로 Easy 문제들이 꽤 남아있다. 오늘은 Queue, DFS, BFS 문제들을 풀어봤다.
933. Number of Recent Calls
문제를 해석하는데 시간이 좀 걸렸는데, 클래스 구현 문제다. RecentCounter는 ping 함수가 호출될 때마다 최근 3000밀리 초 내에 발생한 요청 수를 리턴해줘야 한다.
You have a RecentCounter class which counts the number of recent requests within a certain time frame.
Implement the RecentCounter class:
RecentCounter() Initializes the counter with zero recent requests.int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].
It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.
처음에는 ArrayList를 사용해서 구현했다. ping time을 저장하는 리스트가 있고, 새로운 ping 호출이 들어올 때마다 range에 맞게 index를 조정하도록 했는데, 이 경우 메모리에 ping 데이터를 모두 저장하게 된다. 큐를 사용해서 항상 최근 3000밀리 초 이내에 들어온 ping 요청만 저장하도록 다시 구현했다.
class RecentCounter {
private Queue<Integer> q;
public RecentCounter() {
this.q = new LinkedList<>();
}
public int ping(int t) {
q.offer(t);
int range = t - 3000;
while(q.peek() < range) {
q.poll();
}
return q.size();
}
}시간 복잡도는 ping() 호출 시 while문은 최대 3000번 돌 수 있어서 (time frame 제한) O(3000) = O(1) 이고, 공간 복잡도는 역시 큐에 최대 3000개 ping 호출 시간이 저장될 수 있기 때문에 O(3000) = O(1)이다.
104. Maximum Depth of Binary Tree
이진트리의 최대 깊이를 찾는 문제다.
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
간단히 재귀로 순회하면서 최대 depth인 경우 업데이트를 해주면 된다. 재귀 함수에 max값을 업데이트할 수 있도록 레퍼런스를 인자로 추가해줘야 하는데, 길이가 1인 배열을 사용하는 것이 팁이다.
class Solution {
public int maxDepth(TreeNode root) {
int[] ret = new int[1];
maxDepth(root, 1, ret);
return ret[0];
}
private void maxDepth(TreeNode root, int depth, int[] max) {
if (root == null) {
return;
}
if (depth > max[0]) {
max[0] = depth;
}
maxDepth(root.left, depth+1, max);
maxDepth(root.right, depth+1, max);
}
}시간 복잡도는 O(n), 공간 복잡도는 O(1).
199. Binary Tree Right Side View
이진트리의 각 뎁스별로 가장 오른쪽에 있는 원소들의 리스트를 위에서부터 아래 순서로 리턴하는 문제다.
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
level order traverse가 필요한데, 큐를 사용하되 각 레벨에 있는 노드의 개수만큼만 순회하면 구현이 가능하다.
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) {
return ret;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
int size = q.size();
for(int i=0; i<size; i++) {
TreeNode node = q.poll();
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
if (i == size-1) {
ret.add(node.val);
}
}
}
return ret;
}
}시간 복잡도는 이진트리의 노드 개수를 n개라고 했을 때 모든 노드를 한 번씩 순회하기 때문에 O(n), 공간 복잡도는 큐에서 이진트리의 노드를 저장하고 있다. 큐가 가장 마지막 뎁스에서 가질 수 있는 최대 노드 수를 고려하면 O(2^(logn-1)) = O(n/2) = O(n)이다.
