[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]] 으로 묶일 것이다.

 

그룹으로 다 묵었으면 key가 그룹 번호(그룹에 속한 인덱스의 최소 값)이고 value가 사전순으로 작은 문자가 큰 우선순위를 가지는 우선순위큐인 map을 만든다. value인 우선순위큐에는 문자열 s의 문자들이 들어간다.

 

map을 만들었으면 다시 s문자열을 앞에서부터 탐색하면서 이번에는 탐색중인 인덱스가 속한 그룹번호로 map의 value를 가져온다. 가져온 우선순위 큐의 top을 가져온다.(가져오면서 pop) 작은 문자가 우선순위가 크므로 사전순으로 가장 작은 문자를 가져오게 된다. 이를 정답 문자열의 뒤에 추가하면서 정답 문자열을 만든다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1202.%20Smallest%20String%20With%20Swaps.cpp