🔗 Problem

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

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

// 친구 네트워크

public class BJ4195 {
	
	static int test;
	static int num;
	static int[] parent;
	static int[] level;
	static HashMap<String, Integer> friends = new HashMap<>();		// 이름과 parent를 담는 map
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		test = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for(int i = 0; i < test; i++) {
			
			num = Integer.parseInt(br.readLine());
			friends.clear();
			parent = new int[num * 2];
			level = new int[num * 2];
			Arrays.fill(level, 1);
			
			int idx = 0;
			for(int j = 0; j < num; j++) {
				
				st = new StringTokenizer(br.readLine());
				String a = st.nextToken();
				String b = st.nextToken();
				
				if(!friends.containsKey(a)) {
					parent[idx] = idx;
					friends.put(a, idx++);
				}
				if(!friends.containsKey(b)) {
					parent[idx] = idx;
					friends.put(b, idx++);
				}
				
				union(friends.get(a), friends.get(b));
				
				sb.append(level[findParent(friends.get(a))]).append("\n");
			}
		}
		
		System.out.println(sb.toString());
	}
	
	private static void union(int a, int b) {
		
		int pa = findParent(a);
		int pb = findParent(b);
		
		if(pa == pb) return;
		parent[pb] = pa;			// pb의 부모를 pa로 설정하였으므로
		level[pa] += level[pb];		// pb의 서브트리만큼 pa의 서브트리가 늘어났기에 더해준다.
	}
	
	private static int findParent(int x) {
		
		if(x == parent[x]) return x;
		return parent[x] = findParent(parent[x]);
	}
	
}

📌 Note

시간초과

• 처음에는 전체 트리 생성 후 모든 노드에 대해 root와 같은지 판별하는 방식으로 구현하여 시간초과가 발생하였다.
• 자식 노드 개수를 저장하는 level[]을 만들어서 해결

메모리 효율

• 메모리 초과는 발생하지 않았지만,
  처음에 HashMap<String, String> friends로 각 노드를 저장하여, 즉 부모를 int형이 아닌 String으로(이름 그대로) 저장하여 공간 효율이 좋지 않았다.
• int[] parent를 따로 만들 생각은 했었는데 위 방식이 직관적으로 구현하기 편하다고 생각하여 고집했던 거 같다..

문제 자체는 어렵지 않았으나 놓친 부분이 많았던 문제.
3일 후에 다시 풀어볼 예정.