TMI
얼마 전, 레디스 다중 로그인을 맵(해쉬)를 이용해서 풀어서, 해쉬 문제에 급 관심이 생겼다. 그래서 오늘은 그거 위주로 풀었음
1. 걸그룹 마스터 준석이 - 백준16165
public static class BOJ16165 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 주어지는 걸그룹의 수
int M = Integer.parseInt(st.nextToken()); // 문제의 수
Map<String, ArrayList<String>> map = new HashMap<>();
for (int i = 0; i < N; i++) {
String s = br.readLine(); // 주어지는 그룹의 이름
int memberCount = Integer.parseInt(br.readLine()); // 그룹의 멤버 수
ArrayList<String> members = new ArrayList<>();
for (int j = 0; j < memberCount; j++) {
String memberName = br.readLine();
members.add(memberName);
}
map.put(s, members);
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 문제 개수를 입력받는 부분
for (int i = 0; i < M; i++) {
String given = br.readLine(); // 멤버 혹은 팀 이름
int memberOrTeam = Integer.parseInt(br.readLine()); // 0이면 팀 멤버 다, 1이면 어느팀 소속인지
if (memberOrTeam == 0) {
ArrayList<String> strings = map.get(given);
Collections.sort(strings);
for (String string : strings) {
bw.append(string).append("\n");
// System.out.println(string);
}
} else {
for (String s : map.keySet()) {
ArrayList<String> strings = map.get(s);
if (strings.contains(given)) {
bw.append(s).append("\n");
// System.out.println(s);
break;
}
}
}
}
bw.flush();
br.close();
bw.close();
}
}- 입출력이 매우 많아서 오랜만에 BufferedWriter 사용
- { key(팀이름) : value(멤버이름 어레이리스트)} 사용해서 풀었다.
2. 친구 네트워크 - 백준 4195
틀린 버전
public static class BOJ4195 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 주어지는 문제들의 개수
StringTokenizer st;
for (int i = 0; i < N; i++) {
Map<String, Set<String>> map = new HashMap<>();
int M = Integer.parseInt(br.readLine()); // 주어질 관계도의 수
for (int j = 0; j < M; j++) {
st = new StringTokenizer(br.readLine());
String first = st.nextToken();
String second = st.nextToken();
Set<String> set = map.getOrDefault(first, new HashSet<>());
Set<String> set2 = map.getOrDefault(second, new HashSet<>());
set.add(first);
set2.add(first);
set.add(second);
set2.add(second);
set.addAll(set2);
map.put(first, set);
map.put(second, set);
System.out.println(map.get(first).size());
}
}
}
}- set을 사용해서 무식하게 양쪽다 넣어주는 모습
- 메모리 초과가 발생한다.
이 문제는, 유니온 파인드를 사용해야 한다고 한다.
Union find?
유니온 파인드에 대해서 정확히 이해가 안된 상태라, todo로 남겨두고 나중에 다시 풀어볼 예정. 유니온파인드 문제부터 풀어야겠다
집합의 표현 - 백준 1717
public static class BOJ1717{
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 집합의 개수는 N + 1
int M = Integer.parseInt(st.nextToken()); // M 개만큼의 문제가 주어짐
parent = new int[N+1];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int isOne = Integer.parseInt(st.nextToken());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
if (isOne == 0){
union(first, second);
} else {
if (checkSame(first, second)){ // 같은 루트노드를 공유하는 확인
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
static void union(int a, int b){
a = find(a); // a의 루트노드
b = find(b); // b의 루트노드
if (a != b){
parent[b] = a; // 첫번째놈 a 를 기준으로 유니언하므로, b의 루트노드를 a로 옮겨줌
}
}
static int find(int a){
if (a == parent[a]){
return a;
} else {
return parent[a] = find(parent[a]);
}
}
static boolean checkSame(int a, int b){ // 두 원소가 같은 집합인지 확인
a = find(a);
b = find(b);
return a==b;
}
}-
루트 노드를 향해서 점점 흡수되어 가는 형태
-
유니언 파인드는 (a, b) 와 같은 순서로 주어지는 녀석들을 a의 루트노드로 (a가 루트라면 a로) 병합해 가는 것이다.
-
주의할점은, a의 루트노드로 병합해가는 대상이 b의 루트노드라는 것. 즉, b 루트노드 한 뭉치가 a로 병합된다고 생각해야 한다.
그렇다면 위를 활용해서 못다푼 문제를 다시 풀어보자
public static class BOJ4195_2 {
static int[] parent;
static int[] size;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 주어지는 문제들의 개수
for (int t = 0; t < N; t++) {
int M = Integer.parseInt(br.readLine()); // 주어질 관계도의 수
parent = new int[2 * M]; // 주어지는 관계가 모두 접점이 없는 녀석들일 수 있으므로 2 * M
size = new int[2 * M];
for (int i = 0; i < 2 * M; i++) {
parent[i] = i;
size[i] = 1;
}
Map<String, Integer> map = new HashMap<>();
AtomicInteger currentID = new AtomicInteger();
// 멀티 쓰레드 환경에서 안전한 래퍼 객체
for (int j = 0; j < M; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String first = st.nextToken();
String second = st.nextToken();
// 맵에서 키를 생성함.
// computeIfAbsent 는 키가 없을때만 동작하므로, String 값들을 int 로 관리 가능하게 함
int firstID = map.computeIfAbsent(first, k -> currentID.getAndIncrement());
int secondID = map.computeIfAbsent(second, k -> currentID.getAndIncrement());
// 루트노드를 각각 찾아줌
int parent1 = findParent(firstID);
int parent2 = findParent(secondID);
if (parent1 != parent2) {
union(parent1, parent2); // 루트노드를 병합시킴
}
System.out.println(size[findParent(firstID)]);
}
}
}
static int findParent(int x) {
if (parent[x] != x) {
parent[x] = findParent(parent[x]);
}
return parent[x]; // 루트노드로 업데이트
}
static void union(int x, int y) {
int parentX = findParent(x);
int parentY = findParent(y);
parent[parentY] = parentX;
size[parentX] += size[parentY];
}
}
-
Union Find 사용하기 위해서, 받아오는 String 값들을 map의 computeIfAbsent() 매서드를 통해서 밸류화 해줌
-
나머지 부분은 전형적인 유니온 파인드. 주석으로 설명되어 있다
-
size 부분도 union(x, y)의 x 가 가지고 있는 사이즈에 계속적으로 추가했음
