[백준/JAVA] 해시를 사용한 집합과 맵 10816 숫자 카드 2

나의 답1) 시간 초과

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();
        while(st.hasMoreTokens()) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            sb.append(Collections.frequency(list, num)).append(" ");
        }
        
        System.out.print(sb);
    }
}

 

 

[시간 초과가 발생한 이유]

1. Collections.frequency() 사용의 비효율성

•  Collections.frequency(list, num)은 리스트를 순회하며 num과 같은 값을 하나씩 세는 방식으로 동작한다.
• 리스트의 크기가 N이고, 쿼리의 개수가 M일 때, 각 쿼리마다 리스트 전체를 탐색해야 하므로 시간 복잡도는 O(N X M)이다.
• 문제의 제한 조건에서 N, M 모두 최대 500,000이므로, 최악의 경우 250,000,000번의 연산이 필요하다. 이는 시간 초과를 유발한다.

 

2. ArrayList의 탐색 속도

• ArrayList는 단순 배열 기반 자료구조로, 특정 값의 개수를 세기 위해 리스트 전체를 반복 탐색해야 한다.
• 리스트를 해시 기반 자료구조(예: HashMap)로 변경하면 특정 값에 빠르게 접근할 수 있다.

 

나의 답2) 1232ms (list를 map으로 변경)

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        HashMap<Integer, Integer> map = new HashMap<>();
        while(st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            sb.append(map.getOrDefault(num, 0)).append(" ");
        }
        
        System.out.print(sb);
    }
}

 

 

[코드 설명]

1. HashMap을 사용한 빈도 계산

• map.put(num, map.getOrDefault(num, 0) + 1)를 통해 숫자 카드의 빈도를 한 번에 계산한다.
• 빈도를 미리 계산해 두면, 특정 숫자의 개수를 조회하는데 상수 시간(O(1))이 소요된다.
• +1의 의미
  : 만약 num이 이미 존재한다면, 기존 빈도 값에 1을 더한다. 만약 존재하지 않은다면 기본값 0을 가져온 뒤 1을 더한다.

2. getOrDefault() 사용

• 쿼리 값이 HashMap에 없는 경우 기본값 0을 반환하도록 처리한다.

3. 시간 복잡도

• 숫자 카드 리스트를 한 번 순회: O(N)
• 쿼리 리스트를 한 번 순회: O(M)
• 총합: O(N + M)