[백준/JAVA] 18016 - 숫자 카드 2

백준 10816 - 숫자 카드 2

요구사항

• N개의 숫자 카드 중 M개의 숫자가 각각 몇 개 있는지 출력하는 문제

접근 방식

풀이 1 - HashMap

숫자를 key, 등장 횟수를 value로 저장해서 O(1)로 조회했다.

주의: 반복문 안에서 System.out.println()을 매번 호출하면 I/O 비용이
M번(최대 50만번) 누적되어 시간초과가 발생한다.
→ StringBuilder로 모아서 한 번에 출력해야 한다.

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));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        Map<Integer, Integer> map = new HashMap<>();

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

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            sb.append(map.getOrDefault(target, 0)).append(" ");
        }
        System.out.println(sb);
    }
}

풀이 2 - 이분탐색 (LowerBound / UpperBound)

정렬 후 lowerBound(첫 등장 인덱스) 와 upperBound(마지막 등장 다음 인덱스) 의
차이로 개수를 구했다.

upper - lower = 해당 숫자의 개수

핵심 주의사항

• rt = numbers.length (length-1 아님!)
• while(lt < rt) (<= 아님!)
• 위 두 조건을 지켜야 경계값 처리가 정확하다.

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));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] numbers = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numbers);

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            int count = upper(numbers, target) - lower(numbers, target);
            sb.append(count).append(" ");
        }
        System.out.println(sb);
    }

    public static int lower(int[] numbers, int target) {
        int lt = 0, rt = numbers.length;
        while (lt < rt) {
            int mid = (lt + rt) / 2;
            if (numbers[mid] < target) lt = mid + 1;
            else rt = mid;
        }
        return lt;
    }

    public static int upper(int[] numbers, int target) {
        int lt = 0, rt = numbers.length;
        while (lt < rt) {
            int mid = (lt + rt) / 2;
            if (numbers[mid] <= target) lt = mid + 1;
            else rt = mid;
        }
        return lt;
    }
}

느낀점

• 처음에 System.out.println()을 반복문 안에서 호출해서 시간초과가 발생했다.
  출력이 많은 문제는 항상 StringBuilder로 모아서 한 번에 출력하는 습관을 기르자.
• 이분탐색에서 rt = length와 while(lt < rt) 조건이 헷갈렸다.
  lowerBound/upperBound는 rt를 배열 길이로 설정하고 lt < rt로 순회하는 것이 정석이다.
• HashMap 풀이가 더 간결하지만, lowerBound/upperBound 패턴은
  이분탐색 응용 문제에서 자주 쓰이므로 반드시 익혀두자.