Leetcode 75의 마지막 날이다! Interval 1문제, Dynamic Programming 2문제가 마지막 문제들이다.
435. Non-overlapping Intervals
주어진 배열 intervals가 있을 때, 배열에 들어있는 interval들이 서로 겹치지 않도록 삭제해야 하는 최소 interval의 개수를 구하여라.
Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
intervals를 정렬해야 하는데, 직관적으로는 start_i를 기준으로 정렬하고 overlapping 하는 인터벌을 삭제하는 식으로 구현하였는데, 이 경우 앞에 들어간 interval의 범위가 큰 경우 더 많은 interval을 삭제하게 되는 경우가 있었다. (예를 들어 [[-10, 100], [-5, 5], [-10, 10], [10, 20]] 인 경우 [-10, 100]만 삭제하면 되므로 답은 1이지만 로직상 결과는 3이 나오게 된다.) 관련된 강의 노트도 있으니 참고하자.
고민을 하다가 솔루션을 봤는데, end_i 기준으로 정렬을 하고 있었다. end_i를 기준으로 정렬을 하면 두 interval을 비교한다고 했을 때 항상 앞에 있는 것을 먼저 골라야 한다. 그래야 다음 interval과 overlapping 될 확률이 적기 때문이다. 이때 선택한 값을 k라고 했을 때, 다음에 오는 interval과 k값의 경우는 아래 두 가지로 나눌 수 있다:
1. k가 x보다 작거나 같은 경우: overlap이 없다.
2. k가 x보다 큰 경우: overlap이 있다. 그래서 이 interval을 없애야 한다.
배열을 end_i 기준으로 정렬하고, k값은 최소값으로 정의한다. 그리고 배열을 순회하면서 각 케이스 1, 케이스 2에 대한 로직을 돌면 정답을 구할 수 있다.
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int ret = 0, k = Integer.MIN_VALUE;
for(int i=0; i<intervals.length; i++) {
int x = intervals[i][0];
int y = intervals[i][1];
if (x >= k) {
k = y;
} else {
ret++;
}
}
return ret;
}
}시간 복잡도는 O(nlogn), 공간 복잡도는 자바에서 정렬에 필요한 공간 때문에 O(logn)이 필요하다.
714. Best Time to Buy and Sell Stock with Transaction Fee
주식의 i번째 일 가격을 담은 배열 prices와 주식 거래에 드는 비용 fee가 주어졌을 때 내가 취할 수 있는 최대 수익을 찾아라. 거래는 내가 하고 싶은 만큼 할 수 있지만, 매 번 거래할 때마다 수수료가 든다. 그리고 주식 거래를 동시에 여러 번 할 수 없고 주식을 사려면 반드시 팔아야 한다.
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee. Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). The transaction fee is only charged once for each stock purchase and sale.
솔루션을 보지 않고서는 풀 수 없었던 문제...😭
첫날(prices[0])부터 i번째 날까지 최대 수익은 i-1번째 날 최대 수익과 관련이 있다는 점에서 이 문제를 DP로 풀어야 한다고 예상 가능하다(고 한다). 그리고 i번째 날의 상태는 주식을 들고 있는 상태, 주식을 들고 있지 않을 때 두 상태로 나눠야 하기 때문에 hold, free 두 개의 배열이 필요하다.
i번째 날 주식을 산다면, 주식을 들고 있지 않아야 하므로, hold[i] = free[i-1] - prices[i] 가 된다.
i번째 날 주식을 판다면, free[i] = hold[i-1] + prices[i] - fee 가 된다.
그리고 i번째 날 아무것도 하지 않는 경우도 있기 때문에 hold[i] = hold[i-1], free[i] = free[i-1]이 될 것이다.
그래서 위의 경우들을 모두 고려하면 free[i], hold[i]는 다음과 같이 구할 수 있다.
- free[i] = max(free[i-1], hold[i-1] + prices[i] - fee)
- hold[i] = max(hold[i-1], free[i-1] - prices[i])
초기화할 때는 free[0] = 0, hold[0] = -prices[0] 으로 초기화한다.
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[] free = new int[n], hold = new int[n];
// In order to hold a stock on day 0, we have no other choice but to buy it for prices[0].
hold[0] = -prices[0];
for (int i = 1; i < n; i++) {
hold[i] = Math.max(hold[i - 1], free[i - 1] - prices[i]);
free[i] = Math.max(free[i - 1], hold[i - 1] + prices[i] - fee);
}
return free[n - 1];
}
}시간 복잡도 O(n), 공간 복잡도 O(n)
790. Domino and Tromino Tiling
2x1 도미노와 Trimino 도미노 두 개의 타입이 있다. 이 도미노들을 회전시킬 수도 있다. 정수 n이 주어졌을 때, 2 x n 보드에 타일을 배치할 수 있는 방법의 수를 반환하라. 답변이 매우 클 수 있기 때문에 정답을 10^9 + 7로 나눈 값을 반환한다. 타일을 깔 때 각 사각형은 반드시 타일로 덮여야 한다.
You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.
Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 10^9 + 7.
In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.
솔루션을 안 보고 풀어봤는데, n = 3까지만 보고 모든 경우가 나왔다고 생각했는데, 2 x 4에서 ⌜⎽⌝, ⌞⎺⌟ 두 가지 경우를 생각하지 못했다. 그런데 n=5 까지만 보고도 점화식을 유도할 수 있다는 게 참 대단한 것 같다. 풀이를 보여주려고 n=5까지만 보여준 건지, 진짜 n=5까지만 본 건지 궁금하다. 🧐
n이 4보다 작게 주어질 수 있고 그러면 배열값 할당에서 오류가 날 수 있기 때문에 배열을 n+4로 선언한다. 그 뒤로는 점화식을 따라서 n까지 값을 채워가면 된다.
class Solution {
public int numTilings(int n) {
int mod = 1_000_000_007;
int dp[] = new int[n+4];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for(int i=4; i<=n; i++) {
dp[i] = ((2*dp[i-1])%mod)+dp[i-3];
dp[i] %= mod;
}
return dp[n];
}
}시간 복잡도 O(n), 공간 복잡도 O(n)이다.
Leetcode 75 후기
배지가 생겼다! 다양한 패턴별로 문제를 풀어볼 수 있어서 코딩테스트에 조금 더 자신감이 생긴 것 같다. 중간에 휴가를 가서 하루에 3문제씩 매일 푸는 것은 못했지만, Study plan을 통해서 짧은 시간 집중해서 여러 문제를 풀어볼 수 있으니 좋았다. 리트코드에 문제가 워낙 많이 있으니 앞으로 이런 문제 셋이 많이 생기면 코딩테스트 여정을 시작할 때 도움이 될 것 같다.
