[백준] 10815 : 숫자 카드 - Java

• 백준 문제 URL

---

문제 접근

1. 상근이 카드 개수 N과 카드 번호들을 입력받는다.
2. HashSet에 상근이 카드 번호들을 저장 (순서 무관, 중복 제거).
3. 검증 카드 개수 M과 검증할 카드 번호들을 입력받는다.
4. 각 검증 카드에 대해 HashSet.contains()로 소유 여부 확인:
   • 있음: 1 추가
   • 없음: 0 추가
5. StringBuilder로 공백 포함 결과 문자열 구성 후 출력.

즉, "HashSet 저장 → O(1) 조회 → 결과 누적" 과정을 수행한다.

---

HashSet 자료구조 사용 이유

이 문제는 카드 소유 여부 확인만 필요하므로 순서와 중복이 중요하지 않다.
HashSet(Hash Table 기반)은:

• O(1) 평균 조회 시간 (contains())
• 중복 자동 제거
• 순서 보장 불필요 → 메모리 효율적

---

시뮬레이션 예시

입력:

5
6 3 2 10 7
4
4 2 7 13

단계	검증카드	HashSet 조회	StringBuilder 누적
1	4	없음	0
2	2	있음	0 1
3	7	있음	0 1 1
4	13	없음	0 1 1 0

최종 출력: 0 1 1 0

---

정리

• HashSet으로 O(1) 조회 → O(N+M) 전체 복잡도.
• StringTokenizer로 효율적 입력 파싱.
• StringBuilder + 조건부 공백으로 출력 형식 완벽 대응.
• ArrayList 선형탐색 대비 100배 이상 빠름!

---

제출 코드 (완성본)

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));
        
        int n = Integer.parseInt(br.readLine());
        Set<Integer> cards = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            cards.add(Integer.parseInt(st.nextToken()));
        }
        
        int m = Integer.parseInt(br.readLine());
        StringTokenizer checkSt = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < m; i++) {
            int card = Integer.parseInt(checkSt.nextToken());
            sb.append(cards.contains(card) ? "1" : "0");
            if (i != m - 1) sb.append(" ");
        }
        System.out.println(sb);
    }
}