공부공간

BOJ - 4195 ) 친구 네트워크 본문

알고리즘/Hash

BOJ - 4195 ) 친구 네트워크

개발자가될수있을까? 2020. 7. 2. 13:57


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

 

4195번: 친구 네트워크

문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이

www.acmicpc.net

 


두명의 이름이 들어왔을때 이전 친구 그룹에 속하는지와 속하지 않으면 새로운친구 그룹을 만들면서 진행하는 문제이다

 

F=10만이기때문에 적절한 최적화를해주면 통과할 수 있다..

 

1 ) 두사람이 모두 HashMap에 없는경우

 

2 ) 한쪽만 HashMap에 있는 경우

 

3 ) 둘다 있는경우 

 

세가지로 나누어서 생각해보자.. 

1 ) 경우는 친구 그룹의 크기가 2가 항상 보장된다.

2 ) 경우는 친구 그룹이 결정된 그룹의 크기 +1 이 보장된다.

 3 ) 두 그룹의 합이 다음 친구 그룹의 합이되는게 보장된다.

 

따라서 이름 : 숫자 / 숫자 : 이름의 동적리스트 의 관계로 2개의 Map으로 해결하면 된다.

 


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class 친구네트워크 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st.nextToken());
		StringBuilder sb = new StringBuilder();
		for(int i = 0 ; i < t ; i++) {
			st = new StringTokenizer(br.readLine());
			int tc = Integer.parseInt(st.nextToken());
			HashMap<String, Integer> hs = new HashMap<>();
			
			HashMap<Integer, ArrayList<String>> nameMap = new HashMap<>();
			for(int j = 0 ; j < tc ; j++) {
				st = new StringTokenizer(br.readLine());
				String name1 = st.nextToken();
				String name2 = st.nextToken();
				if(!hs.containsKey(name1) && !hs.containsKey(name2)) {
					// 둘다 없는 경우  j+1로 add
					hs.put(name1, j+1);
					hs.put(name2, j+1);
					nameMap.put(j+1, new ArrayList<String>());
					nameMap.get(j+1).add(name1);
					nameMap.get(j+1).add(name2);
					sb.append("2\n");
				} else if (!hs.containsKey(name1) && hs.containsKey(name2)) {
					int idx = hs.get(name2);
					hs.put(name1, idx);
					nameMap.get(idx).add(name1);
					sb.append(nameMap.get(idx).size() +"\n");
				} else if (!hs.containsKey(name2) && hs.containsKey(name1)) {
					int idx = hs.get(name1);
					hs.put(name2, idx);
					nameMap.get(idx).add(name2);
					sb.append(nameMap.get(idx).size() +"\n");
				} else {
					// 둘다있는경우 큰 쪽으로 Union 해준다.
					
					int idx_1 = hs.get(name1);
					int idx_2 = hs.get(name2);
					if(idx_1==idx_2) {
						sb.append(nameMap.get(idx_1).size() +"\n");
					} else {
						if(nameMap.get(idx_1).size() > nameMap.get(idx_2).size()) {
							for(int k = 0 ; k < nameMap.get(idx_2).size() ; k++) {
								String now = nameMap.get(idx_2).get(k);
								hs.put(now, idx_1);
								nameMap.get(idx_1).add(now);
							}
							nameMap.remove(idx_2);
							sb.append(nameMap.get(idx_1).size() +"\n");
						} else {
							for(int k = 0 ; k < nameMap.get(idx_1).size() ; k++) {
								String now = nameMap.get(idx_1).get(k);
								hs.put(now, idx_2);
								nameMap.get(idx_2).add(now);
							}
	
							nameMap.remove(idx_1);
							sb.append(nameMap.get(idx_2).size() +"\n");
						}
					}
				}
			}
		}System.out.println(sb);
	}

}

Comments