Weekly Contest 305. (2367~2370) (list, graph, dp)

오랜만에 리트코드 컨테스트를 다 풀었습니다.

 

problem 2367. Number of Arithmetic Triplets

 

코드 :

 

class Solution:
    def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
        res = 0
        for i in range(len(nums)-2):
            for j in range(i+1, len(nums)-1):
                for k in range(j+1,len(nums)):
                    if nums[j] - nums[i] == diff and nums[k] - nums[j] == diff:
                        res += 1
        return res

 

설명 : Brute force 알고리즘이 통할 것으로 보여서, Brute force를 사용하였습니다.

O(n^3)이지만, n 자체가 200이기 때문에, n^3을 해도 o(8 * 10^6) 정도로, 충분히 통과될 것이라고 생각되었고,

실제로 통과 되었습니다.

 

problem 2368. Reachable Nodes with Restrictions

Account Login - LeetCode

 

코드 :

from collections import defaultdict

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        res_set = set(restricted)
        e_d = defaultdict(set)
        for edge in edges:
            v1, v2 = edge
            if v1 not in res_set and v2 not in res_set:
                e_d[v1].add(v2)
                e_d[v2].add(v1)
     
    
        count = 0
        stack = [0]
        seen = set()
        
        while stack:
            node = stack.pop()
            seen.add(node)
            count += 1
            
            for n in list(e_d[node]):
                if n not in seen:
                    stack.append(n)
            
        return count

설명 : BFS/DFS 를 사용하면 됩니다. stack을 사용하였음으로, DFS가 되겠습니다.

어떤 것을 사용하는지는 그렇게 중요하지 않을 것으로 봅니다.

restricted list에 들어있는지를 set을 통해서 판단하고, 

seen이라는 set을 통해서 한 번 거쳤던 node는 다시 거치지 않도록 해줍니다.

 

problem 2369. Check if There is a Valid Partition for the Array

Account Login - LeetCode

 

코드 :

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        
        dp = [1] + [0] * len(nums)
        # print(dp)
        for i in range(len(dp)):
            if dp[i] == 1:
                if i + 2 < len(dp):
                    if nums[i] == nums[i + 1]:
                        dp[i+2] = 1
                        
                if i + 3 < len(dp):
                    if nums[i] == nums[i+1] == nums[i+2]:
                        dp[i+3] = 1
                    if nums[i+1] - nums[i] == nums[i+2] - nums[i+1] == 1:
                        dp[i+3] = 1
        # print(dp)

        if dp[-1] == 1:
            return True
        return False

설명 : dp 문제였습니다. 

dp 1d array를 만들어 놓고, 처음에 1을 추가해 주는건, 시작을 해야되기 때문에 그렇습니다.

그 이후 1을 만날 때마다 그 이후 2개나 3개짜리 element를 검사하면서 valid partition을 만날 때마다

1을 dp에다가 업데이트 해주었습니다.

time complexity는 o(n) 입니다.

 

problem 2370. Longest Ideal Subsequence

Account Login - LeetCode

 

코드 :

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        dp = [0] * 26
        
        for c in s:
            diff = ord(c) - ord('a')
            
            min_bucket = 0 if diff - k < 0 else diff - k
            max_bucket = 25 if diff + k > 25 else diff + k
            
            dp[diff] = max(dp[min_bucket:max_bucket+1]) + 1
        # print(dp)
        return max(dp)

설명 :

dp 1d array를 알파벳 수만큼 만듭니다.

각각의 dp의 의미는, 각각 알파벳으로 끝나는 최대의 값을 말합니다.

예를 들어, "acfgd"이고, k=2 이면,

"a"일때 dp[0]을 1, "c"일 때, "a"에서 "e" 사이의 최대값이 1이니깐 dp[1] = 2,

"f"일 때 "d"에서 "h" 사이의 최대값이 0이기 때문에 dp[2] = 1 이런식으로 해서

결국 마지막에 dp의 최대값을 구하면 됩니다.