[CLASS 2: 이분탐색] 백준 10816 숫자 카드(2)

10816번: 숫자 카드(2)

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

 

# 코드

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        TreeMap<Integer, Integer> map = new TreeMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            // map에 없는 키라면 개수를 0 + 1 로 하여 추가
            // map에 있는 키라면 + 1 하여 해당 값을 대체
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int j = 0; j < m; j++) {
            int num = Integer.parseInt(st.nextToken());
            
            if (map.containsKey(num)) {
                sb.append(map.get(num) + " ");
            } else {
                sb.append(0 + " ");
            }
        }
        System.out.println(sb);
        br.close();
    }
}

• 영원한 친구 TreeMap을 이용해 로직을 작성했다.

 

채점해보니 시간복잡도가 상당해서 다른 제출자분의 코드를 참고해 다시 작성했다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[20000001]; // 배열의 모든 요소는 자동으로 0으로 초기화됨
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            // 숫자를 입력받으면 해당 숫자에 +10000000을 해서 그 인덱스의 값을 1 증가
            cards[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(cards[Integer.parseInt(st.nextToken()) + 10000000]).append(' ');
        }
        System.out.println(sb);
        br.close();
    }
}

• 자바에서 int[] 배열을 선언하면, 배열의 모든 요소는 자동으로 0으로 초기화된다는 점을 이용한 코드이다.
• 숫자를 입력받으면 해당 숫자에 +10000000을 해서 그 인덱스의 값을 1 증가시킨다.
• 출력 시에도 동일하게 값에  10000000을 더한 인덱스에서 값을 꺼내오면 된다.
• 인덱스를 통해 값을 꺼내오는 작업에서는 배열의 성능이 매우 뛰어나다는 사실을 기억하자. 배열은 메모리 상에 연속적으로 저장되기 때문에 특정 인덱스에 접근하는 시간이 일정하고 빠르다. 배열에서의 인덱스 접근 시간은 O(1), 즉 상수 시간이다.

 

절반 넘게 줄어들었다