986 https://leetcode.com/problems/interval-list-intersections/
왠지 그리디 문제같이 생긴 list intersection문제이다. 무식하게 풀면 안되고 규칙을 찾은 뒤에 구현하면 된다. 투 포인터를 쓰기는 하는데 그냥 구현하면 된다.. 두개의 리스트가 있을때 겹치는 경우는 first_start <= second_end and second_start <= first_end인 경우이다.
이 경우에 넣어주고 한개씩 뒤로 가면서 끝까지 간다.
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
ret = []
while i < len(firstList) and j < len(secondList):
#print ('i,j =',i,j)
first_start, first_end = firstList[i]
second_start, second_end = secondList[j]
#print(first_start, first_end, second_start, second_end)
if first_start <= second_end and second_start <= first_end:
ret.append([max(first_start, second_start), min(first_end, second_end)])
if first_end <= second_end:
i += 1
else:
j += 1
return ret
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
의 경우에는 근접된 값중 최대의 값을 최대 3번 반복할 수 있다. 연관된 것기리 묶어보면 아래와 같다.
[(15, 15, 15), (9), (10, 10, 10)] 인데 처음의 15는 인덱스 1의 15가 가장크니 인덱스 1의 15를 인덱스 0,2의 값도 15로 변경해서 15이고, 마지막 인덱스 10을 3번 반복한후 남은 중간의 값이 9이다. 이런식으로 partitioning을 해서 합이 최대가 되는 경우를 만드는거다.
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
의 경우에는 arr = [(1), (7,7,7,7), (9,9,9,9), (9,9)] 처럼 나오게 되어 합이 83이 된다.
내가 어떤 값을 얼마나 반복해야 할지 모른다. 만약 가장 큰 수를 찾았다고 해도 이걸 현 위치의 왼쪽으로 k만큼 반복해야할지, 오른쪽으로 k만큼 해야할지, 아니면 왼쪽 오른쪽으로 나눠서 가야할지도 모른다. 그래서 모든 경우의 수를 계산하면서 이미 계산한 값을 기반으로 뒷 값을 만들어가면서 푼다.
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
arr_len = len(arr)
dp = [0] * (arr_len)
for i in range(arr_len):
max_temp = 0
# j는 k값이 될수 있는 후보군들이다. 최소 1번반복부터, k번까지 반복하거나, 최대한 반복해도 기준이 되는 i보다는 왼쪽에 있어야 한다.
# k=3이라고 가정하면 i=0일때 k의 후보군인 j=1, i=1일때 k의 후보군인 j=1,2, i=2일때 k의 후보군인 j=1,2,3이 될수있다.
# i=0일때 k의 후보군인 j=1만 가능한 이유는 j가 1보다 커지면 현재 기준인 i보다 오른쪽으로 가기 때문이다.
# 마찬가지로 i=1일때 j=1,2가 가능한 이유는 j=3이면 현재 i=1보다 오른쪽 인덱스이기 때문이다.
for j in range(1, 1 + min(k, i+1)):
# max_temp는 기준점 i보다 왼쪽에 있는 값들을 대상으로 가장 큰 값을 가져온다.
max_temp = max(max_temp, arr[i - j + 1])
# dp[i]의 최대값은 기준점 i가 j보다 큰 위치일때(i>=j) 이전에 만든 최대값인 dp[i-j]에 현재 배열에 있는 최대값 max_temp에 k의 후보군인 j번만큼 곱한 값을 더한 값으로 설정한다.
dp[i] = max(dp[i], (dp[i - j] if i >= j else 0) + max_temp * j)
return dp[arr_len-1]
복잡하다.
1329 https://leetcode.com/problems/sort-the-matrix-diagonally/
이것도 무식하게 풀었다가 이번에 하나 알아간다. 행, 열로 순회하면서 행, 열이 i, j라고 했을때 i-j가 대각 행렬을 뜻한다. 이를 이용해 대각 행렬의 값을 저장한 후 소팅후 하나하나 다시 만들어준다. 이해가 안가면 아래에 주석처리해놓은 print를 주석 풀고 프린트후 비교해보자.
class Solution:
def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
diagonal_dict = {}
for i in range(len(mat)):
for j in range(len(mat[0])):
if i-j not in diagonal_dict:
diagonal_dict[i-j] = []
diagonal_dict[i-j].append(mat[i][j])
#for k,v in diagonal_dict.items():
# print(k,v)
for k,v in diagonal_dict.items():
v.sort()
for i in range(len(mat)):
for j in range(len(mat[0])):
mat[i][j] = diagonal_dict[i-j].pop(0)
return mat