[백준] S4 10816번 숫자 카드2 (Java)

https://www.acmicpc.net/problem/10816

👉 문제

우선 상근이가 가지고 있는 카드에서, 몇 개 가지고 있는 숫자 카드인지 구해야 할 카드 번호가 주어진다.

여기서 처음에 생각한 방법은 상근이가 가지고 있는 카드의 숫자를 HashMap의 Key로 사용하고 그에 따른 개수를 Value로 하고, 이후에 입력받는 카드의 숫자가 Key로서 존재하면 Value를 아니면 0 StringBuilder에 넣어 출력하도록 했더니 시간 초과 없이 정답을 맞힐 수 있었다.

그 이후에 시간을 줄일 수 있을까 싶어서 원소 자체를 인덱스로 삼아서 개수를 카운팅 하는 방식을 사용해 보았다. 가장 빠르고 수의 범위가 제한되어 있어서 사용할 수 있었던 방법이지만, 메모리 낭비가 심하긴 한 것 같다..

👉 풀이

1. 상근이가 가지고 있는 카드의 숫자와 개수를 각각 HashMap의 Key와 Value로 사용. 이후 입력받는 카드의 숫자가 Key로서 존재하면 Value를 아니면 0을 출력.

package Baekjoon;

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

public class _10816_1 {

    static String num;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < N; i++) {
            num = st.nextToken();

            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < M; i++) {

            num = st.nextToken();

            if (map.containsKey(num)) {
                sb.append(map.get(num));
            } else {
                sb.append(0);
            }

            sb.append(' ');
        }

        System.out.println(sb);
    }
}

2. 원소 자체를 인덱스로 삼아서 개수를 카운팅 하는 방식

package Baekjoon;

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

public class _10816_2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[20000001];

        for (int i = 0; i < N; i++) {
            arr[Integer.parseInt(st.nextToken()) + 10000000]++;
        }

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

        for (int i = 0; i < M; i++) {
            sb.append(arr[Integer.parseInt(st.nextToken())+10000000]).append(' ');
        }

        System.out.println(sb);
    }
}

👉 성능

채점번호 : 69763673 - 방법 2 : 원소 자체를 인덱스로 카운팅
채점번호 : 69763350 - 방법 1 : HashMap 사용