[java] 1764. 듣보잡

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

---

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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int N = Integer.parseInt(st.nextToken());
        String[] seeNot = new String[N];
        int M = Integer.parseInt(st.nextToken());
        String[] hearNot = new String[M];

        for (int i=0 ; i<N ; i++) {
            seeNot[i] = br.readLine();
        }
        for (int i=0 ; i<M ; i++) {
            hearNot[i] = br.readLine();
        }

        Map<String, Integer> commonValuesCount = new HashMap<>();
        for (int i=0 ; i<N ; i++) {
            for (int j=0 ; j<M ; j++) {
                if (seeNot[i].equals(hearNot[j])) {
                    commonValuesCount.put(seeNot[i], commonValuesCount.getOrDefault(seeNot[i], 0) + 1);
                }
            }
        }

        List<String> sortedCommonValues = new ArrayList<>(commonValuesCount.keySet());
        Collections.sort(sortedCommonValues);

        System.out.println(sortedCommonValues.size());

        for (String value : sortedCommonValues) {
            System.out.println(value);
        }
    }
}

omg 시간초과 뜸

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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int N = Integer.parseInt(st.nextToken());
        HashSet<String> seeNotSet = new HashSet<>();
        int M = Integer.parseInt(st.nextToken());
        HashSet<String> hearNotSet = new HashSet<>();

        for (int i=0 ; i<N ; i++) {
            seeNotSet.add(br.readLine());
        }
        for (int i=0 ; i<M ; i++) {
            hearNotSet.add(br.readLine());
        }

        seeNotSet.retainAll(hearNotSet);

        ArrayList<String> sortedCommonValues = new ArrayList<>(seeNotSet);
        Collections.sort(sortedCommonValues);

        System.out.println(sortedCommonValues.size());

        for (String value : sortedCommonValues) {
            System.out.println(value);
        }
    }
}

시간초과의 이유는 arrayList의 사용이었다.

 

HashSet의 contains()는 O(1), ArrayList의 contains()는 O(n)이다. HashSet은 map을 기반으로 구현되고, ArrayList는 indexOf()를 사용해서 contain여부를 결정한다고 한다.

 

HashSet

HashSet은 중복되지 않는 값만 저장하며, 순서를 보장하지 않습니다. 집합(Set)의 개념을 구현한 자료구조입니다.

특징:

• 중복된 값을 허용하지 않습니다. 하나의 요소는 최대 한 번만 저장될 수 있습니다.
• 순서를 유지하지 않기 때문에 요소의 순서에 의존하는 작업에는 적합하지 않습니다.
• 검색, 삽입, 삭제 연산의 시간 복잡도는 일반적으로 O(1)입니다. (상수 시간 내에 수행됨)
• HashSet은 해시 함수를 이용하여 값을 저장하고 검색하기 때문에, 큰 데이터 세트에서 빠른 검색 속도를 제공합니다.

주요 메서드:

• add(E e): 요소 추가
• remove(Object o): 요소 삭제
• contains(Object o): 요소 포함 여부 확인
• size(): 요소 개수 반환

ArrayList

ArrayList은 동적 배열(Dynamic Array)을 구현한 클래스로, 순서를 유지합니다. 배열과 비슷한 성능을 가지지만 크기를 자동으로 조정할 수 있는 장점을 가지고 있습니다.

특징:

• 중복된 값을 허용합니다. 같은 값이 여러 번 저장될 수 있습니다.
• 요소의 순서를 유지하며, 요소의 삽입 및 삭제는 비교적 느릴 수 있습니다.
• 배열과 비슷한 인덱스를 통한 접근이 가능하므로, 요소에 빠르게 접근할 수 있습니다.
• 배열의 크기가 초과되면 자동으로 크기를 늘려주기 때문에, 동적으로 크기를 관리할 수 있습니다.

주요 메서드:

• add(E e): 요소 추가
• remove(Object o): 요소 삭제 (첫 번째로 발견되는 요소 삭제)
• get(int index): 지정된 인덱스에 위치한 요소 반환
• size(): 요소 개수 반환