intro : Map을 사용할지, Set을 사용할지 고민해 보는게 좋다.

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000 000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

문제 풀이 1 (Map을 이용한 문제풀이)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        br.readLine();
        String[] getCartSplit = br.readLine().split(" ");
        int findCount = Integer.parseInt(br.readLine());
        int[] result = new int[findCount];
        String[] findCardSplit = br.readLine().split(" ");

        Map<Integer, Boolean> cardMap = new HashMap<>();
        Map<Integer, Boolean> findMap = new LinkedHashMap<>();

        for (String getCard : getCartSplit) cardMap.put(Integer.parseInt(getCard), true);
        for (String findCard : findCardSplit) findMap.put(Integer.parseInt(findCard), true);

        int index = 0;
        for (Integer findKey : findMap.keySet()) {
            Boolean check = cardMap.getOrDefault(findKey, false);
            if (check) {
                result[index] = 1;
            }
            index++;
        }

        StringBuilder sb = new StringBuilder();
        for (int value : result) {
            sb.append(value).append(" ");
        }
        System.out.println(sb);
    }
}

문제 풀이 2 (Set을 이용한 문제풀이)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int getCardCount = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Set<String> getCardSet = new HashSet<>();
        for (int i = 0; i < getCardCount; i++) getCardSet.add(st.nextToken());

        StringBuilder sb = new StringBuilder();

        int findCardCount = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < findCardCount; i++) {
            boolean check = getCardSet.contains(st.nextToken());
            if (check) {
                sb.append("1").append(" ");
            } else {
                sb.append("0").append(" ");
            }
        }

        System.out.println(sb);
    }
}

문제 해석

주어진 조건을 잘 살펴보면 N(1 ≤ N ≤ 500,000), M(1 ≤ M ≤ 500,000) 즉 N 과 M의 길이가 각각 50만씩, 이중 반복문으로 카드의 존재여부를 확인하고자 하는 로직을 구성한다면 ? 단순히 생각했을때만 해도 2500억 번의 연산횟수가 시도된다.(물론 정확하게는 아니고 대략적인 값이다.)

1억번당 1초의 연산 속도를 가정한다면 이 문제는 단순 반복문으로 풀 수 있는 문제가 아닌것을 눈치 해야한다. 그렇다면 시간 복잡도가 1에 수렴하면서 빠르게 존재여부를 확인할 수 있는 자료구조는 무엇이 있을까 ?

바로 Hash 자료구조이다. 보통 Hash 자료구조에는 크게 두가지가 있는데 Map 과 Set이 존재한다. Map.get() 메소드는 1의 시간복잡도에 수렴하며, Set.contains() 메소드 또한 1의 시간복잡도에 수렴한다 (보통 그렇다.) 이 포인트를 잘 생각하여 상근이가 가지고 있는 카드가 숫자카드에 존재하는 카드인지 체크하는 로직을 구성하는것이 문제 풀이의 옳은 방법이 된다.

초기 문제풀이1번에서는 LinkedHashMap을 통해 자료구조를 구성해서 문제풀이를 시도했는데, 문제를 풀고나니 굳이 순서를 지키면서 변수를 구성해야 될 필요도 없다는 것을 알게되었으며, 문제 조건에서 주어진 값이 중복된 값이 없다고 하였으니 Map이 아닌 Set을 통해 풀이를 구성하는게 이 문제에 더 적합하다고 생각된다.

I am visible

contact

문제

입력

출력

문제 풀이 1 (Map을 이용한 문제풀이)

문제 풀이 2 (Set을 이용한 문제풀이)

문제 해석