[leetcode][1202] Smallest String With Swaps
문제 : https://leetcode.com/problems/smallest-string-with-swaps/ 만약 [(1,3), (1,2)] 라는 pairs 배열이 입력으로 주어진다면 s[1], s[2], s[3] 에 있는 문자들은 direct로는 아니더라도 서로 change 할 수 있다. ex) (2, 3) 을 바꾸려면 (1, 3), (1,2) (1,3)을 바꾸면 (2,3)을 바꾼 결과가 된다. 따라서 Union-Find로 문제를 풀 수 있다. 모든 pairs를 탐색하면서 Union-Find로 한 다리 건너서라도 바꿀 수 있는 인덱스들을 그룹으로 묶는다. 같은 그룹은 속한 그룹의 s 문자열의 최소 인덱스를 가진다. 위 예제에서는 [[0], [1,2,3]] 으로 묶일 것이다. 그룹으로 다 묵었으면 k..
2019. 9. 23.
