[백준(JAVA)] 1764번: 듣보잡

문제

✔ 난이도 - Silver 4

설명

처음에는 중첩for문을 사용해서 작성함 -> 시간초과!
HastSet를 사용하자

split 보다는 StringTokenizer가 메모리를 덜 잡아먹는다.
속도도 더 빠르다고 하는데 대용량의 데이터가 아니면 크게 차이는 없음.
그러나 성능이 중요한 백준에서는 StringTokenizer를 사용하는게 더 좋을 듯

• split 사용
  
• StringTokenizer 사용
  

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //듣도보도 못할 사람 넣을 리스트
        ArrayList<String> list = new ArrayList<>();
        
        //듣도 못할 사람 넣을 해시셋
        HashSet<String> hs = new HashSet<>();
        for(int i = 0; i < N; i++){
            hs.add(br.readLine());
        }

        //보도 못할 사람 입력받으면서 듣도 못할 사람인지 체크하고 맞다면 결과리스트에 넣음
        for(int i = 0; i < M; i++){
            String notSee = br.readLine();
            if (hs.contains(notSee)){
                list.add(notSee);
            }
        }

        Collections.sort(list);

        int count = list.size();
        sb.append(count).append("\n");
        for(String s : list){
            sb.append(s).append("\n");
        }

        System.out.println(sb);
    }
}

시간복잡도 ⏰

O(N log N)

• 결과리스트 정렬 부분

TIL💡

📌HashSet.contains()

내부적으로 HashSet 구현은 HashMap 인스턴스를 기반으로 한다
평균적으로 HashSet의 contains()는 O(1) 시간 내에 실행

ArrayList.contains()

내부적으로 ArrayList는 indexOf(object) 메서드를 사용하여 개체가 목록에 있는지 확인
indexOf(object) 메서드는 전체 array를 반복하고 각 요소를 equals(object) 메서드와 비교
ArrayList.contains() 메서드는 O(n) 시간이 필요
(https://www.baeldung.com/java-hashset-arraylist-contains-performance)