[백준] 1764 듣보잡 : 실버 4 (자바) - 문자열 / 해시

✔️ 문제 설명

문제

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

입력

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

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

출력

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

예제 입력 1 복사

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1 복사

2
baesangwook
ohhenrie

 

✔️ 문제 풀이

►ArrayList 사용한 코드 (시간초과)

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;

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());
        int m = Integer.parseInt(st.nextToken());

        ArrayList<String> notEverHeard = new ArrayList<>();
        ArrayList<String> notEverHeardSeen = new ArrayList<>();

        for(int i = 0; i<n; i++){
            notEverHeard.add(br.readLine());
        }
        for(int i = 0; i<m; i++){
            String str = br.readLine();
            if(notEverHeard.contains(str))
                notEverHeardSeen.add(str);
        }

        Collections.sort(notEverHeardSeen);

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

        for(int i = 0; i<notEverHeardSeen.size(); i++){
            System.out.println(notEverHeardSeen.get(i));
        }
    }
}

 

[시간 복잡도 계산]

1. 입력 처리
   - BufferedReader와 StringTokenizer를 사용해 n과 m 값을 입력받음
   -> 시간 복잡도 : O(1)
2.  듣도 못한 사람 리스트 작성
   - for(int i = 0; i < n; i++) 반복문을 통해 n개의 이름을 notEverHeard 리스트에 추가
   -> 시간 복잡도 : O(n)
3.  보도 못한 사람 체크
   - for(int i = 0; i < m; i++) 반복문을 통해 m개의 이름을 입력받아 notEverHeard 리스트에서 포함 여부를 확인.
   - ArrayList.contains 메서드가 내부적으로 선형 탐색을 수행하기 때문에, 최악의 경우 O(n)
   -> 시간 복잡도 : O(m⋅n)
4.  결과 정렬
   -  notEverHeardSeen을 정렬
    -> 시간 복잡도 : 평균 O(nlogn), 최악의 경우 O(n^2)
5.  결과 출력
    -> 시간 복잡도 : O(k)

→ 총 시간 복잡도 : O(m⋅n+klogk)

 

여기서, 시간 복잡도를 줄이기 위해서 보도 못한 사람 체크 로직에서 ArrayList.contains를 HashSet.contains로 수정하면,  O(m⋅n) 을 O(m⋅1)로 줄일 수 있다.

 

►HashSet 사용한 코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;

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());
        int m = Integer.parseInt(st.nextToken());

        HashSet<String> notEverHeard = new HashSet<>();
        ArrayList<String> notEverHeardSeen = new ArrayList<>();

        for(int i = 0; i<n; i++){
            notEverHeard.add(br.readLine());
        }
        for(int i = 0; i<m; i++){
            String str = br.readLine();
            if(notEverHeard.contains(str))
                notEverHeardSeen.add(str);
        }

        Collections.sort(notEverHeardSeen);

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

        for(int i = 0; i<notEverHeardSeen.size(); i++){
            System.out.println(notEverHeardSeen.get(i));
        }
    }
}