[Baekjoon] 24571_Good Groups

문제(출처: https://www.acmicpc.net/problem/24571)

---

< Good Groups >

 

문제 풀이 

 

HashMap 각각에 같은 조에 속해있어야 하는 학생들과, 같은 조에 속해있으면 안되는 학생들을 저장한다.

조를 입력받으며 제약 조건을 위반하는지 확인한다.

 

* 제약 조건에 이름이 중복될 수 있다.

 

my solution (Java)

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

public class _24571_ { // Good Groups

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int x = Integer.parseInt(bf.readLine());

		HashMap<String, ArrayList<String>> same = new HashMap<>();
		for (int i = 0; i < x; i++) {
			st = new StringTokenizer(bf.readLine());

			String a = st.nextToken();
			String b = st.nextToken();

			if (same.containsKey(a)) {
				same.get(a).add(b);
			} else {
				ArrayList<String> list = new ArrayList<>();
				list.add(b);

				same.put(a, list);
			}

			if (same.containsKey(b)) {
				same.get(b).add(a);
			} else {
				ArrayList<String> list = new ArrayList<>();
				list.add(a);

				same.put(b, list);
			}
		}

		int y = Integer.parseInt(bf.readLine());

		HashMap<String, ArrayList<String>> diff = new HashMap<>();
		for (int i = 0; i < y; i++) {
			st = new StringTokenizer(bf.readLine());

			String a = st.nextToken();
			String b = st.nextToken();

			if (diff.containsKey(a)) {
				diff.get(a).add(b);
			} else {
				ArrayList<String> list = new ArrayList<>();
				list.add(b);

				diff.put(a, list);
			}

			if (diff.containsKey(b)) {
				diff.get(b).add(a);
			} else {
				ArrayList<String> list = new ArrayList<>();
				list.add(a);

				diff.put(b, list);
			}
		}

		int g = Integer.parseInt(bf.readLine());

		int result = 0;
		for (int i = 0; i < g; i++) {
			st = new StringTokenizer(bf.readLine());

			ArrayList<String> list = new ArrayList<>();

			while (st.hasMoreTokens()) {
				list.add(st.nextToken());
			}

			for (int j = 0; j < list.size(); j++) {
				ArrayList<Integer> temp = new ArrayList<>();
				if (same.containsKey(list.get(j))) {
					for (int k = 0; k < same.get(list.get(j)).size(); k++) {
						if (!list.contains(same.get(list.get(j)).get(k))) {
							result += 1;
							temp.add(k);
						}
					}
					for (int k = temp.size() - 1; k >= 0; k--) {
						same.get(same.get(list.get(j)).get(temp.get(k))).remove(list.get(j));
						same.get(list.get(j)).remove(temp.get(k));
					}
				}

				temp.clear();
				if (diff.containsKey(list.get(j))) {
					for (int k = 0; k < diff.get(list.get(j)).size(); k++) {
						if (list.contains(diff.get(list.get(j)).get(k))) {
							result += 1;
							temp.add(k);
						}
					}
					for (int k = temp.size() - 1; k >= 0; k--) {
						diff.get(diff.get(list.get(j)).get(temp.get(k))).remove(list.get(j));
						diff.get(list.get(j)).remove(temp.get(k));
					}
				}
			}
		}
		System.out.println(result);
	}
}

변수)
x : 같은 조에 속해야 할 학생들의 조건 개수
same : 같은 조에 속해야 하는 제약사항
a, b : 학생 이름
y : 다른 조에 속해야 할 학생들의 조건 개수
diff : 다른 조에 속해야 하는 제약사항
g : 반에 있는 조의 개수
temp : 위반한 제약사항
result : 위반한 제약사항 개수

 

같은 조에 속해야 할 학생들의 조건 개수를 입력받고 그 개수만큼 제약 조건을 입력받아 HashMap에 저장한다. 이때, 이름이 중복될 수 있으므로 key값으로 String, value로 ArrayList를 저장하며 양방향으로 저장한다. 

 

다른 조에 속해야 할 학생들의 조건 개수를 입력받고 그 개수만큼 제약 조건을 입력받아 HashMap에 저장한다. 위와 마찬가지 형태로 저장한다.

 

반에 있는 조의 개수를 입력받아 그 개수만큼 조를 입력받는다. 조를 탐색하며 제약 조건을 위반하는지 확인한다. 

 

최종 위반한 제약사항 개수인 result를 출력한다.

---

---