Problem Solving/LeetCode

Today's Challenge

fabichoi 2022. 11. 14. 23:45

 

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        rows, cols = defaultdict(list), defaultdict(list)
        for s, (r, c) in enumerate(stones):
            rows[r].append(s)
            cols[c].append(s)
            
        seen, n = set(), len(stones)
        
        def dfs(s):
            if s in seen:
                return 0
            seen.add(s)
            
            r, c = stones[s]
            
            for ss in chain(rows[r], cols[c]):
                dfs(ss)
            
            return 1
        
        c = sum(dfs(s) for s in range(n))
        
        return n - c

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

 

Most Stones Removed with Same Row or Column - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

완탐 같았는데 N이 너무 큼.. 
솔루션을 보니 DFS 였음 =_=;

 

반응형