class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
self.ret = 0
def inorder(node):
if not node:
return 9999999999, -9999999999
l_min, l_max = inorder(node.left) # 왼쪽자식최소, 왼쪽자식최대
r_min, r_max = inorder(node.right) # 오른쪽자식최소, 오른쪽자식최대
min_min = min(l_min, r_min) # 최소중에 최소를 구함.
max_max = max(l_max, r_max) # 최대중에 최대를 구함.
min_gap = abs(node.val - min_min) # 현재 노드와의 차를 구해서
max_gap = abs(node.val - max_max)
if min_gap < 100000: # 나같은경우는 리프노드에서 9999999999를 리턴하라고 했다. 문제범위가 100000이하이니 이 위의 값들은 너무 커서 쓸때없는값으로 판단하고 버리기 위해 이렇게 짬
self.ret = max(min_gap, self.ret)
if max_gap < 100000:
self.ret = max(max_gap, self.ret)
return min(node.val, min_min), max(node.val, max_max)
inorder(root)
return self.ret
public int maxAncestorDiff(TreeNode root) {
return dfs(root, root.val, root.val);
}
public int dfs(TreeNode root, int mn, int mx) {
if (root == null) return mx - mn;
mx = Math.max(mx, root.val);
mn = Math.min(mn, root.val);
return Math.max(dfs(root.left, mn, mx), dfs(root.right, mn, mx));
}
왜 이렇게 할 생각을 못했는지 모르겠는데 내 답은 leaf부터 값을 만들어가며 root로 올라온다. 그런데 얘 답은 반대로 root에서 시작해서 leaf까지 내려간다. 그리고 min, max는 인자로 전달을 한다. 이런식으로 코드를 짜니 가독성이 훨씬 좋아지도 코드도 간결해진다.. 대단하다.
1525 https://leetcode.com/problems/number-of-good-ways-to-split-a-string/
문자열을 두 부분으로 나눴을때 각각 가지고 있는 distinct한 영단어의 갯수가 동일한 경우의 수를 구하는 문제이다. 제한조건을 살펴보면 길이가 100000이라 무식하게 풀면 통과 못한다.
0부터 인덱스 i까지 몇개의 distinct한 영단어를 가지고 있는지 저장하는 prefix리스트,
끝에서부터 인덱스 0까지 몇개의 distinct한 영단어를 가지고 있는지 저장하는 suffix리스트를 만든 후에..
인덱스를 0부터 끝까지 돌아가면서 인덱스가 i일때 prefix리스트의 영단어와 suffix의 영단어 갯수를 비교했을때 값이 동일하면 증가시켜주는방법으로 푼다.
class Solution:
def numSplits(self, s: str) -> int:
prefix, suffix = [], []
pre_set, suf_set = set(), set()
len_s = len(s)
for i in range(len_s):
pre_set.add(s[i])
suf_set.add(s[len_s - i - 1])
prefix.append(len(pre_set))
suffix.append(len(suf_set))
#print(prefix)
#print(suffix)
ret = 0
for i in range(len_s-1):
#print(i, len_s-2-i)
if prefix[i] == suffix[len_s-2-i]:
ret += 1
return ret
1884 https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors/
오랫만에 보는 dp문제이다. 문제가 무슨소리를 하는지 이해하는데 좀 걸렸다. 계란이 두개만 존재하며, 계란을 떨어뜨려서 계란이 깨지는 층을 알아내는 문제인데, 확실하게 알아내야 하며, 그중 최소의 move를 구하는 문제이다. 처음에는 이분 탐색으로 풀면 되겠는데? 싶다가 이게 아니라는걸 깨달았다. 모든 케이스를 계산해야 하며, 중복해서 계산하지 않도록 dp에 저장해놓고 푼다.
총 100층이고 만약 50층에서 떨어뜨렸는데 계란이 깨졌다고 해보자. 남은 계란은 1개이고, 이 계란이 깨지기 전에 깨지는 층을 확실히 알아내려면 1층부터 올라가면서 49층까지 일일히 다 떨어뜨려봐야한다. 근데 첫번째 50층에서 떨어진 계란이 깨지지 않으면? 51~100층사이로 해보면 된다. 근데 계란은 두개이고, 몇 층이 최적화 층인지는 모른다. 51층, 55층, 60층 이렇게 5씩 올라가다가 60층에서 깨지면 55~60으로 해보면 될거고.. 75층에서 던져봤는데 깨지면 51~74층까지 전부 다 해봐야 한다. 이중에서 가장 낮은 수를 구하는 것인데 어느 케이스가 낮을지 모르니까 전부 구해본다.
1. 계란이 한개가 남거나 현재 층이 1층 이하이면 현재 층값인 n이 확실히 알수있는 경우의 수이다.
1) 현재 층이 5층, 계란이 1개남으면 -> 5번을 실험해봐야하므로 n번을 해야한다.
2) 현재 층이 1층이면 계란을 0층에서 떨궈본다. 계란이 깨지면 0층이 깨지는 층임을 알수있다.(1번실험함.) 현재 층이 0층이면 실험할 필요도 없이(0번실험) 깨지는 층이 0층임을 알수있다.
2. 현재가 100층이면, 아래의 모든 층을 돌아가면서, 계란이 깨진경우와 깨지지 않은경우로 계산해볼수 있다.
i가 1~n사이의 층이라고 가정하자.
확실하게 알수있는 최솟값은 max(계란이 깨진경우 i-1층에서의 값, 계란이 안깨진경우 현재 층에서 검사한 i층만큼 내려가서 계산해본 값)이다. 두 케이스중에 확실하게 아는 케이스를 구하기 위해 max함수로 둘중 큰 값을 골라준다.
그리고 이런식으로 코드를 짜면 된다.
class Solution:
dp = [[0]*3 for i in range(1001)]
def twoEggDrop(self, n: int, egg=2) -> int:
if egg == 1 or n <= 1:
return n
if self.dp[n][egg] != 0:
return self.dp[n][egg]
min_val = 9999999
for i in range(1, n+1):
min_val = min(min_val, max(1 + self.twoEggDrop(i-1, egg-1), 1 + self.twoEggDrop(n-i, egg)))
self.dp[n][egg] = min_val
return self.dp[n][egg]