리트코드 75 12일 차, DP 2문제와 Heap을 사용하는 문제를 풀어봤다. DP는 쉬운 문제는 쉬운데 어려운 문제는 감이 안 잡히는 게 문제다..
62. Unique Paths
m x n 배열 위에 로봇이 있다. 로봇은 최초에 좌상단 모서리(grid[0][0])에 있다. 로봇은 우하단 모서리(grid[m-1][n-1])로 가려고 한다. 로봇은 한 번에 오른쪽 또는 아래로 이동할 수 있다. m, n이 주어졌을 때 로봇이 우하단 모서리로 갈 수 있는 가능한 고유한 경로의 수를 구해라.
There is a robot on an m x n grid.
The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]).
The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
이 문제의 경우 점화식을 쉽게 만들 수 있었다. grid[m][n] 에서 고유한 경로의 수를 sol[m][n]에 저장한다고 하자. 로봇은 오른쪽 또는 아래 방향으로만 갈 수 있기 때문에 sol[m][n]에 도달하는 방법은 왼쪽에서 오거나(sol[m][n-1]), 위에서 오는(sol[m-1][n]) 방법뿐이다. 그래서 sol[m][n] = sol[m][n-1] + sol[m-1][n] 이 된다. sol 배열의 첫 번째 열, 첫 번째 행을 가는 경로는 1가지뿐이므로 1로 초기화한다. 그리고 sol을 차례대로 채워주면 고유한 경로의 수를 구할 수 있다.
class Solution {
public int uniquePaths(int m, int n) {
int[][] sol = new int[m][n];
for(int i=0; i<m; i++) {
sol[i][0] = 1;
}
for(int j=0; j<n; j++) {
sol[0][j] = 1;
}
for(int r=1; r<m; r++) {
for(int c=1; c<n; c++) {
sol[r][c] = sol[r-1][c] + sol[r][c-1];
}
}
return sol[m-1][n-1];
}
}시간 복잡도를 보면 sol 첫 행 초기화 O(n), 첫 열 초기화 O(m), 그리고 고유한 경로 구하는데 O(mn)이 소요된다. 따라서 시간복잡도는 O(mn)이 된다. 그리고 공간 복잡도는 sol 배열 저장 때문에 O(mn)이다.
198. House Robber
당신은 전문 털이범(?)이다. 각 집에는 일정 금액의 돈이 있고, 인접한 두 집을 모두 터는 경우 자동으로 경찰에 연락이 가게 된다. 각 집에 보관된 돈을 저장하고 있는 배열이 있을 때, 보안 경보를 울리지 않으면서 훔칠 수 있는 돈의 최대양을 구하라.
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
점화식을 도출해보자. i 번째 집에서 훔칠 수 있는 돈의 최대양이 어떻게 될까? nums 배열의 길이가 n일 때, 동일한 크기의 배열 sums를 만들고 0 번째 집부터 i 번째 집까지 훔친 돈의 최대양을 저장하고 있다고 하자. sums[i]는 어떻게 구할 수 있을까? 문제의 조건을 보면 i번째 집에서 돈을 훔친다면 인접한 돈을 훔칠 수 없기 때문에 sums[i] = sums[i-2] + nums[i] 이 될 것이다. 만약 i-1번째 집에서 돈을 훔쳤다면 i번째 집에서는 돈을 훔칠 수 없다. 따라서 sums[i] = sums[i-1]이 될 것이다. 두 경우 중 값이 더 큰 값을 취하면 되니까 sums[i] = max(sums[i-2] + nums[i], sums[i-1])이 된다.
sums[i] 배열을 계산하기 전에 sums[0], sums[1]을 초기화해야 한다. sums[0]은 nums[-1]이 없기 때문에 sums[0] = nums[0]이 될 것이다. 그리고 sums[1]은 0번째 집의 돈이 많은지 1번째 집의 돈이 더 많은가에 따라 nums[0], nums[1] 둘 중 하나의 값이 될 것이다. 나머지 2부터 n-1까지는 점화식으로 차례대로 채우면 된다.
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (len == 1) {
return nums[0];
}
int[] sums = new int[len];
sums[0] = nums[0];
sums[1] = nums[0] < nums[1] ? nums[1] : nums[0];
for(int i=2; i<len; i++) {
sums[i] = Math.max(sums[i-2]+nums[i], sums[i-1]);
}
return sums[len-1];
}
}시간 복잡도는 O(n), 공간 복잡도는 O(n).
2336. Smallest Number in Infinite Set
모든 양수인 정수를 가진 집합이 있다. SmallestInfiniteSet class를 다음과 같이 구현한다:
SmallestInfiniteSet() 생성자는 모든 양수인 정수를 가진 SmallestInfiniteSet 객체를 초기화한다. popSmallest() 메서드는 이 집합에 저장된 가장 작은 정수를 집합에서 제거하고 리턴한다. addBack() 메서드는 이 무한 집합에 들어있지 않은 양수인 정수를 추가한다.
You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].
Implement the SmallestInfiniteSet class:
SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.int popSmallest() Removes and returns the smallest integer contained in the infinite set.void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.
우선순위 큐(최소힙)를 사용하면 쉽게 구현할 수 있다. minNum은 popSmallest() 메서드를 호출했을 때 무한 집합의 최소값을 저장하기 위해 사용한다. 그리고 pq는 addBack() 메서드를 호출했을 때 추가된 값을 저장한다. 이 때 저장할 값이 pq에 이미 존재하지 않는지 꼭 확인해야 한다.(테스트케이스 실패 ㅠ)
class SmallestInfiniteSet {
private int minNum = 1;
private PriorityQueue<Integer> pq = new PriorityQueue<>();
public SmallestInfiniteSet() {
}
public int popSmallest() {
if (pq.size() == 0) {
return minNum++;
}
return pq.poll();
}
public void addBack(int num) {
if (num < minNum && !pq.contains(num)) {
pq.offer(num);
}
}
}클래스 메서드 구현 문제라서 어떻게 시간 복잡도, 공간 복잡도를 계산해야 하나 고민하다가 설루션을 좀 참고했다. 😅 popSmallest() 함수의 호출 횟수를 m, addBack() 함수의 호출 횟수를 n이라고 하자. 최악의 경우 pq에는 원소가 n개 저장돼 있을 수 있다. 그러면 popSmallest() 함수의 시간 복잡도는 O(mlogn)이다. 그리고 addBack()은 O(nlogn)이라서 최종 시간 복잡도는 O((m+n)logn)이 된다. 공간 복잡도는 pq에 원소가 n개 저장될 수 있으므로 O(n)이 된다.
