[백준] 숫자 카드 2

---

문제링크: https://www.acmicpc.net/problem/10816

---

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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보다 작거나 같다.

출력

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

예제 입력 1 복사

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1 복사

3 0 0 1 2 0 0 2

import java.io.*;  

public class NumberCard {  
    static final byte[] buf = new byte[12]; // int는 10자리까지 가능 + 알파  
    static final int[] cardCount = new int[20000001];  
    static final int offset = 10_000_000;  
    static final FastReader fr = new FastReader();  
    public static void main(String[] args) throws Exception {  
        int N = fr.nextInt();  
        for (int i = 0; i < N; i++) {  
            cardCount[fr.nextInt() + offset]++;  
        }  
        int M = fr.nextInt();  
        long start = System.currentTimeMillis();  
        BufferedOutputStream os = new BufferedOutputStream(System.out);  
        for (int i = 0; i < M; i++) {  
            int result = cardCount[fr.nextInt() + offset];  
            if (result == 0) {  
                os.write('0');  
            } else {  
                int len = 0;  
                while (result > 0) {  
                    buf[len++] = (byte) ((result % 10) + '0');  
                    result /= 10;  
                }  
                for (int j = len - 1; j >= 0; --j) os.write(buf[j]);  
            }  
             os.write(' ');  
        }  
        os.flush();  
        System.out.println(System.currentTimeMillis() - start + "ms");  
    }  

    // 초고속 입력  
    static class FastReader {  
        private static final byte[] buf = new byte[1 << 16];  
        private static final BufferedInputStream in = new BufferedInputStream(System.in);  
        private static int idx = 0, len = 0;  

        int nextInt() throws IOException {  
            int n = 0;  
            byte c;  
            boolean neg = false;  
            while ((c = read()) <= 32);  
            if (c == '-') {  
                neg = true;  
                c = read();  
            }  
            do n = n * 10 + (c - '0');  
            while ((c = read()) > 32);  
            return neg ? -n : n;  
        }  

        private byte read() throws IOException {  
            if (idx == len) {  
                len = in.read(buf);  
                idx = 0;  
            }  
            return buf[idx++];  
        }  
    }  
//    public static void main(String[] args) throws IOException {  
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
//        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
//  
//        int N = Integer.parseInt(br.readLine());  
//        String[] inStr = br.readLine().split(" ");  
//        int[] input = new int[N];  
//        for (int i = 0; i < N; i++) {  
//            input[i] = Integer.parseInt(inStr[i]);  
//        }  
//  
//  
//        int[] cardCount = new int[20000001];  
//        int offset = 10_000_000;  
//        for (int i = 0; i < N; i++) {  
//            cardCount[input[i] + offset]++;  
//        }  
//        int M = Integer.parseInt(br.readLine());  
//  
//        String[] checkStr = br.readLine().split(" ");  
//        int[] check = new int[M];  
//        for (int i = 0; i < M; i++) {  
//            check[i] = Integer.parseInt(checkStr[i]);  
//        }  
//  
//        for (int i = 0; i < M; i++) {  
//            bw.write(Integer.toString(cardCount[check[i] + offset]));  
//            if (i < M - 1) bw.write(" ");  
//  
//        }  
//        bw.flush();  
//        bw.close();  
//  
//    }  

}

기본 구조

• 1차원 int 배열(cardCount) + offset(-위치 대치)
• FastReader(BufferedInputStream 기반)
• BufferedOutputStream으로 직접 바이트 출력
• 자리수 분해 후 역순으로 출력

최적화 과정

1) 버퍼/입출력 방식 개선

• System.out → BufferedOutputStream 전환
• write 호출을 최소화하여 대량 데이터 출력 속도 향상

2) 자리수 변환/출력 최적화

• String.vlaueOf/Integer.toString 사용 안함
• 숫자를 직접 자리별로 쪼개어 buf에 저장 후, 역순으로 출력

3) FastReader 내 입력 파싱 로직 강화

• 음수 입력 안전 처리, 불필요한 분기 제거
• read() 시 버퍼가 소진될 때만 실제 입력 I/O 발생

4) static 변수 재사용 등 미세 최적화

• buf, cardCount 등을 static으로 선언, GC 및 재할당 최소화

---

한계 인식

• 백준 기준 320ms대 기록까지 도달

---

극한 최적화 코드 분석

• 커뮤니티/1등권 소스코드 분석
  • 2차원 배열(MOD 분할) 활용 → 캐시 효율, 메모리 로컬리티 극대화
  • DataInputStream/DataOutputStream으로 직접 바이트 입출력, 별도 출력 버퍼(outBuffer) 도입
  • 자리수 변환 시 비트연산(<<, &, ~) 적극 사용

---

핵심 개념 정리

• MOD: 1차원 인덱스를 2차원으로 분할, 배열 파편화 및 캐시 효율 향상
• 비트연산: 곱하기/나누기 등 산술연산을 시프트/AND/NOT 등 비트 단위로 대체하여 실행 속도 증가

---