Leetcode 75를 시작한 지 벌써 일주일째. 벌써 21 문제를 풀었다. 18일만 더 풀면 된다. 한 가지 문제 패턴을 하루에 모두 풀지 않는 이유는 장기 기억 관점에서 Spaced Repetition이 유리하기 때문이다. 그래서 다양한 유형의 문제를 번갈아가면서 풀면서 모든 패턴을 푸는 방법을 장기적으로 기억하는 게 목표다.
700. Search in a Binary Search Tree
이진 검색 트리에서 검색하는 문제.
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
이진 검색 트리의 순회를 연습할 수 있는 문제다.
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return root;
}
if (root.val == val) {
return root;
}
if (root.val < val) {
return searchBST(root.right, val);
}
return searchBST(root.left, val);
}
}트리의 노드 개수가 n일 때, 시간 복잡도는 O(n), 공간 복잡도는 O(1).
215. Kth Largest Element in an Array
주어진 배열에서 k번째로 큰 원소를 찾는 문제다.
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
min heap을 사용해서 배열의 원소들을 넣는다. min heap의 크기가 k개를 초과하면 원소를 제거한다. 그러면 min heap의 top에 k 번째로 큰 원소가 있다.
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a,b) -> a-b);
for(int n : nums) {
pq.offer(n);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
}원소의 개수를 n개라고 할 때, 우선순위 큐(min heap)에 원소를 넣는데 많아야 O(logk) 걸리기 때문에 시간 복잡도는 O(nlogk), 공간 복잡도는 O(k)가 된다.
1926. Nearest Exit from Entrance in Maze
미로 안에서 입구에서 가장 가까운 출구까지의 경로의 길이를 찾는 문제다. 미로는 2차원 문자 배열로 주어지고 빈 칸은 점('.')으로 표시하고 벽은 더하기('+')로 표시한다. 만약 경로가 없으면 -1을 반환한다.
You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.
In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.
Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.
전형적인 BFS 문제라고 할 수 있다. BFS 문제를 풀 때 주의할 점은 visited 배열에 방문 여부를 언제 처리할 것인지가 있다. 큐에서 뽑았을 때 방문을 처리하면 중복적으로 큐에 들어갈 수 있기 때문에 꼭 큐에 넣으면서 visited 배열에 체크를 해야 한다.
class Solution {
private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0,1}};
public static class Path {
int r;
int c;
int step;
public Path(int r, int c, int step) {
this.r = r;
this.c = c;
this.step = step;
}
}
public int nearestExit(char[][] maze, int[] entrance) {
Queue<Path> q = new LinkedList<>();
int r = maze.length, c = maze[0].length;
boolean[][] visited = new boolean[r][c];
visited[entrance[0]][entrance[1]] = true;
q.offer(new Path(entrance[0], entrance[1], 0));
while(!q.isEmpty()) {
Path pos = q.poll();
if (pos.r == 0 || pos.r == r-1 || pos.c == 0 || pos.c == c-1) {
if (pos.r != entrance[0] || pos.c != entrance[1]) {
return pos.step;
}
}
for (int[] dir : dirs) {
int newr = pos.r + dir[0];
int newc = pos.c + dir[1];
if (newr >= 0 && newr <r && newc >= 0 && newc < c &&
maze[newr][newc] == '.' && !visited[newr][newc]) {
visited[newr][newc] = true;
q.offer(new Path(newr, newc, pos.step+1));
}
}
}
return -1;
}
}미로의 가로 길이를 c, 세로 길이를 r이라고 했을 때 entrance에서부터 모든 경로를 순회해야 하므로 시간 복잡도는 O(rc), 공간 복잡도는 visited 배열을 사용하기 때문에 O(rc)가 된다.
