릿코드Leetcode (3) 썸네일형 리스트형 Union Find [파이썬] 547. Friend Circles 릿코드 leetcode [2] leetcode.com/problems/friend-circles/ Union Find 문제 Friend Circles - 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 유니온 파인드 개념: kakunblog.tistory.com/16 class Solution(object): def findCircleNum(self, M): sets = [i for i in range(len(M))] def find(x): if x == sets[x]: return x set.. Union Find [파이썬] 684. Redundant Connection 릿코드 leetcode [1] leetcode.com/problems/redundant-connection/ Union Find를 이용해서 풀기 유니온 파인드 개념: kakunblog.tistory.com/16 class Solution(object): def findRedundantConnection(self, edges): sets = [0] * (len(edges)+1) def find(x): if sets[x] == 0: return x return find(sets[x]) for x, y in edges: u = find(x) v = find(y) if u == v: return [x, y] sets[u] = v 다른 유니온 파인드 문제: kakunblog.tistory.com/20 [파이썬] 1299. Replace Elements with Greatest Element on Right Side idx 0부터 n-1 까지 가면서 그 idx를 기준으로 오른쪽에있는 elements들 중 가장 큰 값을 arr[idx] 값으로 바꿔준다 => 복잡도 O(N^2) 복잡도를 줄이기 위해서 idx를 n-2부터 0까지 가면서 그 idx를 기준 오른쪽에 있는 elements들 중 가장 큰 값을 구해준다. => O(N) class Solution(object): def replaceElements(self, arr, mx=-1): for i in range(len(arr) - 1, -1, -1): arr[i], mx = mx, max(mx, arr[i]) return arr 이전 1 다음
