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 였음 =_=;
반응형