[Java] HashMap 사용해보기 (BOJ-10815 숫자 카드)

자바의 HashMap 자료구조 사용해서 BOJ-10815 숫자 카드 풀기

오늘은 백준 10815번 숫자 카드 문제를 풀어보았습니다. BOJ-10815 숫자 카드

문제를 간단히 요약하자면,

N개의 숫자 카드들 가지고 있을 때, M개의 숫자를 입력받아 각 숫자가 N개의 숫자 카드들 중에 있는 지 없는 지 여부를 출력하는 문제입니다.

일반적인 방법으로는 N개의 숫자 카드를 오름차순 정렬한 뒤, M개의 숫자들을 차례대로 binary search 등의 방법으로 탐색하는 해결법이 있습니다.

그러나 자바에서 제공하는 자료구조인 HashMap을 사용하면 시간을 단축시킬 수 있을 것이라 생각해서 HashMap 사용법을 익히는 겸, HashMap을 사용하여 문제를 해결해봤습니다.

HashMap이란?

HashMap은 java.util 패키지에 속한 컬렉션 클래스입니다.

Map의 인터페이스 한 종류이며, HashMap의 각 entry들은 (key, value)의 형태인 데이터로 이루어져 있습니다.

이름에서 나타나듯 Hashing을 사용하기 때문에 빠른 데이터 탐색에 유리한 자료구조입니다.

HashMap 생성하기

import java.util.HashMap;

가장 먼저 당연히 HashMap을 사용하기 위해 import 해줍니다.

HashMap<String, Integer> owned = new HashMap<>();

(key, value) 형태의 데이터를 저장하기 때문에, 선언 시에도 key, value에 대한 타입을 지정해주어야 합니다.

하지만 이 문제에서 각 숫자의 존재 여부를 확인하기 위해선 각 숫자를 key로 하여 key만 사용하면 되기 때문에, value의 타입과 값은 중요하지 않습니다.

제가 key는 숫자인데 타입을 String으로 한 이유는, Integer 타입으로 선언했을 때보다 메모리와 시간 측면에서 모두 조금 더 나은 성능을 보였기 때문입니다!

가장 아래가 String형, 가장 위가 Integer형을 사용했을 때입니다.

Integer 타입으로 선언하면 HashMap을 생성할 때, 검색할 때 매번 String 타입의 입력을 Integer.valueOf() 함수를 호출하여 Integer형으로 변환해야 하는데, 이로 인해 오히려 시간이 더 소요되는 것 같습니다.

HashMap에 데이터 추가하기

StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());

for (int i=0; i<n; i++) {
    owned.put(st.nextToken(), 0);
}

숫자들을 한 줄 입력 받은 뒤, 하나씩 put() 함수를 이용하여 key와 value를 설정하여 데이터를 추가합니다. value의 값은 중요하지 않으므로 저는 0으로 통일했습니다.

이때 만약 key의 값이 중복되는 데이터가 추가되면, 기존의 해당 key의 value가 새로 갱신되는 성질이 있습니다.

HashMap에서 데이터 검색하기

st = new StringTokenizer(br.readLine());
for (int i=0; i<m; i++) {
	if (owned.get(st.nextToken()) != null) {
    	sb.append("1 ");		//sb는 Stringbuiler입니다.
    } else {
    	sb.append("0 ");
    }
}

찾고자 하는 숫자들을 한 줄 입력 받은 뒤, 하나씩 get() 함수를 사용하여 HashMap에서 숫자를 검색합니다. get() 함수는 key값을 매개변수로 가지는데, 해당 key값을 가진 entry가 HashMap 안에 있으면 그 key의 value를 return하고, 없으면 null값을 return하는 성질을 가지고 있습니다.

따라서 get()의 return값이 null인 지를 체크하며 답을 출력하게 됩니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

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

        int n, m;
        HashMap<String, Integer> owned = new HashMap<>();

        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++) {
            owned.put(st.nextToken(), 0);
        }

        m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<m; i++) {
            if (owned.get(st.nextToken()) != null) {
                sb.append("1 ");
            } else {
                sb.append("0 ");
            }
        }
        System.out.println(sb.toString());
    }
}