[백준 - 10815] 숫자 카드 - Java

문제 설명

 

10815번: 숫자 카드

 

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

class Main {

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n];

        StringTokenizer st1 = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) { // O(N)
            cards[i] = Integer.parseInt(st1.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int[] results = new int[m];

        Map<Integer, Integer> map = new HashMap<>();
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) { // O(M)
            map.put(Integer.parseInt(st2.nextToken()), i);
        }

        for (int card : cards) { // O(N)
            if (map.containsKey(card))
                results[map.get(card)] = 1;
        }

        for (int result : results) { // O(M)
            bw.write(result + " ");
        }
        bw.flush();
        bw.close();
    }
}

 

 

풀이 회고

저는 해당 문제를 해시 맵 자료구조를 통해서 해결할 수 있었습니다. 우선 문제에서 요구하는 것은 정수 M개가 주어졌을 때, 각각의 정수가 상근이가 가지고 있는 숫자 카드 N개 중 하나인지 아닌지를 구하는 것입다. 이때 M개의 각각의 정수별로 숫자 카드에 해당하는 게 있으면 1, 해당되는 게 없으면 0을 출력하도록 해야합니다. 즉, 이 문제는 어떤 정수(M개)가 어떤 정수 배열(N개)에 포함되는 게 있는지 없는지를 체크하는 "탐색" 문제입니다.

 

이때 문제에서 주어진 제한 조건은 상근이가 가지고 있는 숫자 카드의 개수는 1 <= N <= 500,000이며, 상근이가 가지고 있는 숫자 카드인지 아닌지를 체크할 숫자의 개수는 1 <= M <= 500,000입니다. 만일 완전 탐색으로 푼다면 M개의 숫자를 하나씩 N개의 숫자와 일치하는지 체크해주어야 하므로 최악의 경우 500,000 * 500,000 = 2,500억번의 연산을 해야합니다.

 

문제에서 주어진 시간 제한은 2초입니다. (CPU별로 다르지만) C언어 기준 보통 10억번의 연산을 했을 때 1초가 걸린다고 생각했을 때 완전 탐색은 어림도 없는 방법입니다. 따라서 시간복잡도 O(logN)의 이분 탐색이나 O(1)의 해시 탐색으로 접근해볼 수 있을 것입니다. 앞서 언급했던 것 처럼 저는 이 중에서 해시 탐색을 사용했습니다.

 

우선 상근이가 가지는 숫자 카드 N개의 수를 cards 배열에 저장하였습니다. 데이터의 개수가 많은 만큼 입출력 API는 BufferedReader와 BufferedWriter를 사용했습니다. (사실 평상시에는 귀찮아서 Scanner를 주로 사용합니다. 😂) 이후 체크할 숫자 M개의 수를 "해시 맵" 자료구조에 저장시켰는데, Key 값으로 입력받은 정수 값을 저장했고 Value 값으로 입력받은 정수 값의 인덱스(index)를 저장시켰습니다. 이는 추후에 탐색 성공 시(N개의 수와 일치 한다면) 해당 인덱스별로 1을 할당해주기 위함이었습니다.

 

이제 상근이가 가지고 있는 숫자 카드를 체크하면 되는데, 사실 M개의 숫자로 N개를 체크하나 N개의 숫자로 M개를 체크하나 동일하므로 저는 상근이가 가지고 있는 숫자 카드로 M개의 숫자와 일치하는지 안하는지를 체크해주도록 했습니다. 이때 해시 맵 API containsKey를 이용하면 O(1)의 시간복잡도로 빠르게 체크해줄 수 있습니다. 이를 코드로 나타내면 다음과 같습니다.

 

        for (int card : cards) { // O(N)
            if (map.containsKey(card))
                results[map.get(card)] = 1;
        }

 

결론적으로 해시 맵에 card라는 정수가 존재하면 결과값을 저장하고 있는 배열의 해당 인덱스의 값에 1을 할당해주면 됩니다. 이때 기본적으로 정수형 배열은 0으로 초기화되므로 존재하지 않는 경우에는 아무런 처리도 하지 않아도 됩니다.

 

 

 

참고자료

• https://www.acmicpc.net/problem/10815