Baekjoon1717
layout: post title: Baekjoon1717 —
집합 표현하기
Step1: Problem Analysis
-n은 노드의 개수, m은 union 또는 find 연산의 횟수를 의미.
-0은 union연산, 1은 find연산을 의미!
-입력:노드 개수, 연산 횟수, 명령 종류 및 관련 노드 연결.
-출력: 같은 집합일시 YES, 다른 집합일시 NO
Solution
-Union-Find
Union: 각 노드 해당 집합의 길이를 size array에 저장해 놓았다. 그 두 개의 집합의 크기를 비교해 더 작은 집합을 더 큰 집합이 흡수!
Find: 만약 대상 노드의 index와 value가 같으면 그냥 return. 다르면 재귀적으로 탐색해 타고 타고 가서 대표 노드를 찾아 return
-답 구하기
Exist(a,b) 함수를 만들어서 대표 노드가 같다면 같은 집합을 의미하므로 True! 아니라면 다른 집합이므로 False 출력!
- Step2: Solve Manually
- Step3: Pseudo Code
- Step4: Implement Code
- 시간초과 나는 코드
- 아마도 이 코드의 경우, union()을 할 때 집합의 크기를 size배열 value를 비교하는 방식이라 그런 게 아닐까 싶다.
“https://gist.github.com/growingpenguin/702198bc849d6df042df21a72c20d1d1.js” 정답 코드 - union시 대표 노드를 찾아 각 대표노드를 연결하는 방식