[백준] 집합과 맵_2

서론

---

집합과 맵 5~8문제

---

10816 : 숫자 카드2

---

문제

---

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

10816번: 숫자 카드 2

---

해설

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(st.nextToken());
            if (map.get(input) != null){
                map.replace(input, map.get(input)+1);
            }
            else {
                map.put(input, 1);
            }
        }
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(map.get(num)==null){
                sb.append(0).append(" ");
            }
            else {
                sb.append(map.get(num)).append(" ");
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

N개의 수를 입력받고, 해당 수의 개수를 Map에 저장해준다.

이때, 해당Map에 이미 Key로 존재한다면, map.replace(input, map.get(input)+1) 을 통해 원래 개수에 1개를 추가해준다.

그리고, M개의 수를 입력받고, 해당 수를 Key로 Map에 존재한다면, 해당 Key에 대응되는 Value를 출력하고,

없다면, 0을 출력해준다.

---

1764 : 듣보잡

---

문제

---

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

1764번: 듣보잡

---

해설_1

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();

        for (int i = 0; i < N; i++) {
            set1.add(br.readLine());
        }
        for (int i = 0; i < M; i++) {
            String tmp = br.readLine();
            if (set1.contains(tmp)) {
                set2.add(tmp);
            }
        }
        String str[] = set2.toArray(new String[0]);
        Arrays.sort(str);
        StringBuilder sb = new StringBuilder();
        sb.append(str.length).append("\n");
        for(String s : str){
            sb.append(s).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

해당 풀이는 Set을 2개 만들어, set1에 포함된 값만 set2에 추가하는 방식을 사용하였으며,

이를 toArray를 통해 배열로 만든 후, 정렬하여 출력하였습니다.

---

해설_2

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();

        for (int i = 0; i < N; i++) {
            set1.add(br.readLine());
        }
        for (int i = 0; i < M; i++) {
            set2.add(br.readLine());
        }
        set2.retainAll(set1);
        String str[] = set2.toArray(new String[0]);
        Arrays.sort(str);
        StringBuilder sb = new StringBuilder();
        sb.append(str.length).append("\n");
        for(String s : str){
            sb.append(s).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

해당 풀이는 Set의 내장함수인 retainAll(교집합)을 사용하고, 이를 정렬하였다.

---

해설_3

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new TreeSet<>();

        for (int i = 0; i < N; i++) {
            set1.add(br.readLine());
        }
        for (int i = 0; i < M; i++) {
            String tmp = br.readLine();
            if (set1.contains(tmp)) {
                set2.add(tmp);
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(set2.size()).append("\n");
        for(String s : set2){
            sb.append(s).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

이번에는 직접 정렬을 하지 않고, TreeSet을 사용하여 출력해주었다. (TreeSet은 기본적으로 오름 차순 정렬이 된다고 함) 

---

1269 : 대칭 차집합

---

문제

---

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

1269번: 대칭 차집합

---

해설_1

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        Set<Integer> A = new HashSet<>();
        Set<Integer> B = new HashSet<>();
        Set<Integer> tmp = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            A.add(num);
            tmp.add(num);
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            B.add(Integer.valueOf(st.nextToken()));
        }

        A.removeAll(B);
        B.removeAll(tmp);
        StringBuilder sb = new StringBuilder();
        sb.append((A.size() + B.size()));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

가장 먼저 풀어본 풀이는, Set을 3개 사용하는 것으로 조금 비효율적이다.

Set의 차집합을 구하는 removeAll 함수를 사용하기 위해, Swap()과 비슷하게 임시로 저장해둘 set이 필요하며, 

말 그대로, A-B, B-A의 개수를 구하는 것으로 문제를 가장 단순하게 이해하고 풀이하였다.

---

해설_2

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Set<Integer> set = new TreeSet<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            set.add(Integer.valueOf(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            Integer tmp = Integer.valueOf(st.nextToken());
            if (set.contains(tmp)) {
                set.remove(tmp);
            }
            else {
                set.add(tmp);
            }
        }
        bw.write(String.valueOf(set.size()));
        bw.flush();
        bw.close();
    }
}

두번째 풀이는, set을 하나만 사용하며, set에 A의 원소들을 저장한 후, B의 원소와 같은 원소가 A에 들어있다면,

이를 remove하며, 그렇지 않으면 추가하면, 결과적으로 대칭 차집합의 원소만 Set에 저장될 것이므로,

해당 사이즈를 출력한다.

위와 비교해서 메모리를 적게 쓰는 것을 확인할 수 있다.

---

해설_3

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Set<Integer> set = new TreeSet<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            set.add(Integer.valueOf(st.nextToken()));
        }
        int cnt = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            Integer tmp = Integer.valueOf(st.nextToken());
            if (set.contains(tmp)) {
                cnt++;
            }
        }
        bw.write(String.valueOf(N + M - 2 * cnt));
        bw.flush();
        bw.close();
    }
}

마지막은, 해설_2와 비슷하게 Set에 A의 원소를 저장하고, B의 원소가 Set에 있다면, cnt를 증가시킨다.

이는 (A+B - A∩B == A∪B) 이며, A∪B -  A∩B == 대칭 차집합 이라는 것을 이용한 방법이다. 

즉,  A + B - 2 * A∩B 이다 (N * M - 2 * cnt)

---

11478 : 서로 다른 부분 문자열의 개수

---

문제

---

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

11478번: 서로 다른 부분 문자열의 개수

---

해설

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String s = br.readLine();
        Set<String> set = new HashSet<>();
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                set.add(s.substring(j, i));
            }
        }
        bw.write(String.valueOf(set.size()));
        bw.flush();
        bw.close();
    }
}

문자열을 입력받고, 2중 for문을 순회하는데, 먼저 첫번째 for문은 만들려는 부분 문자열의 길이를 설정하는 것이다.

그리고, j는 입력받은 문자열의 시작 위치를 설정하는 것이며, 이를 예시로 표를 만들어보면 아래와 같다.

ex) s = "ababc";

j \ i	1	2	3	4	5
0	(1) a	(2) ab	(4) aba	(7)  abab	(11)  ababc
1		(3) b	(5)  ba	(8)  bab	(12)  babc
2			(6)  a	(9)  ab	(13)  abc
3				(10)  b	(14)  bc
4					(15)  c

중복되는 것을 set.add()하면 추가되지 않으며, 추가되지 않는 것은 위에 취소선 표시를 하였다.

---

결론

---

자바의 컬렉션에 대해서 어느 정도는 알고 있다고 생각했는데, 아직 부족한 것 같다는 생각이 들었다.

그래서 다음에는 컬렉션에 대해서 알아보아야겠다.

---