백준 10816 - 숫자 카드 2 ( Java )

 

안녕하세요 besforyou입니다

 

이번 글에서는 백준 문제 10816 숫자 카드 2번 풀이를 소개하겠습니다

 

---

문제 해설

 

N개의 숫자 카드가 먼저 주어지고 M개의 숫자가 주어지는데 N개의 숫자카드 중에서 주어진 숫자와 같은 숫자가 적힌 숫자 카드가 몇 개 있는지 찾는 문제이다.

 

---

문제 풀이

 

단순하게 N개의 숫자 카드를 배열에 저장하고, M개의 숫자가 주어질때마다 배열을 순차 검색해서 같은 숫자의 개수를 세는 방식은 시간 초과가 나온다.

 

N개의 숫자카드가 주어지고 M개의 숫자가 주어질때 순차 검색으로 문제를 푸는 알고리즘의 시간 복잡도는 O(NM)이다. 

1 <= N <= 500,000 , 1 <= M <= 500,000 이므로 매우 많은 시간이 걸릴 수 밖에 없다.

 

많은 데이터를 빠르게 처리해야하므로 순차 검색으로 탐색하지 말고 해쉬 맵을 사용하자.

 

해쉬 맵을 이용 하면 탐색하는데 드는 시간이 O(N)에서 O(logN)으로 줄어드므로 매우 효율적으로 데이터를 탐색할 수 있다.

 

 

---

코드

 

import java.util.Map;
import java.util.HashMap;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    public static int N, M;
 
    public static void main(String [] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());                // N 값을 입력받는다.
 
        String [] split = br.readLine().split(" ");            // 2번째줄을 문자열로 읽고 " "을 기준으로 split. split 배열에는 각각의 숫자카드가 문자열 형식으로 저장되게 된다.
        Map<Integer, Integer> map = new HashMap<>(N);        // 길이가 N인 해쉬맵 생성
 
        for ( int i = 0 ; i < N ; i++ ) {
            int number = Integer.parseInt(split[i]);        //    숫자카드 값을 정수형으로 파싱한다.
            if (map.containsKey(number)) {                    // 해쉬 맵에 이미 숫자카드 값이 있다면,
                map.replace(number, map.get(number) + 1);    // value값을 1 증가시켜 덮어쓴다.
            } else {
                map.put(number, 1);                            // 해쉬 맵에 해당 값이 아직 저장된적이 없다면 새로운 key, value 쌍을 저장한다.
            }
        }
 
        StringBuilder stb = new StringBuilder();
        M = Integer.parseInt(br.readLine());        // M값을 읽는다.
        split = br.readLine().split(" ");            // 4번째 줄을 문자열로 읽고 " " 기준으로 split해서 저장
 
        for ( int i = 0 ; i < M ; i++ ) {
            int number = Integer.parseInt(split[i]);    // 각 숫자를 파싱
            if (map.containsKey(number)) {                // 해쉬 맵에 해당 숫자가 존재하면
                stb.append(map.get(number));            // 해당 숫자의 value를 문자열에 append
            } else {
                stb.append(0);                            // 해쉬 맵에 해당 숫자가 저장된적 없으면 0 append
            }
 
            stb.append(" ");
        }
        System.out.println(stb);        // 정답 
    }
}
 

 

---

결과