https://www.acmicpc.net/problem/4195

문제 자체의 난해함은 없었지만 최대 20만개의 입력을 빠르게 처리할 수 있어야했다.

입력을 문자열로 주는데 이런 문제는 보통 hashMap을 사용해야 편하게 풀 수 있다.

첫 접근 때 bfs를 사용해봤는데 역시 시간복잡도가 터져서 다른 방법으로 유니온 파인드를 사용했다.

유니온 파인드를 사용하면 연결성을 쉽게 파악할 수 있지만 갯수는 파악할 수 없다고 생각했기 때문에 연결 따로, 연결된 노드 관리 따로 해야하는 줄 알았다.

코드

해쉬맵에 해당 사용자가 있는지 확인하고 없으면 넣어주고 있으면 mapping된 값을 가져왔다.

입력받을 때 첫 번째로 들어오는 친구인지, 이미 들어왔던 친구인지 구분해서 처리한다.

# 코드 제출 결과

ps.

1페이지의 코드는 더욱 빨라서 왜 그런지 분석했다.
유니온 파인드는 부모 자식을 관리하는 배열을 초기화할 때 해당 번째로 초기화할 수도 있지만 전체를 -1로 초기화할 수 있다.

이 초기화를 했을 때 장점은 부모가 자식의 갯수를 확인할 수 있다는 점이다.

ex)

값이 [0 1 2 3 4 5] 인 배열이 있다.
유니온 파인드의 set 배열을 -1 -1 -1 -1 -1 -1로 초기화한 후
0 1 2와 3 4 5를 결합한다고 가정한다.

set 배열에서 부모는 set의 자식 값을 취하고,
set의 자식 위치는 부모의 번호를 저장한다.

0 <=1 <=2 순으로 저장하고 4<=3<=5 순으로 저장한다.
0 1 2 3 4 5
-2 0 -1 -1 -1 -1

0 1 2 3 4 5
-3 0 0 -1 -1 -1
=================
0 1 2 3 4 5
-3 0 0 4 -2 -1

0 1 2 3 4 5
-3 0 0 4 -3 4

마지막으로 두 집합을 0 <= 4로 유니온 파인드하면

0 1 2 3 4 5
-6 0 0 4 0 4

---

-1로 초기화 후 유니온 파인드를 하는 방법은 이미 알고 있었지만 부모의 값이 곧 자식의 갯수임을 잊고 있었다.

# 수정된 코드 제출 결과