[BaekJoon] 10816번 숫자 카드 2 문제풀이 (Success)

10816번: 숫자 카드 2

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] iArr;
 
    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());
 
        iArr = new int[N];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            iArr[i] = Integer.parseInt(st1.nextToken());
        }
 
        int M = Integer.parseInt(br.readLine());
 
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            bw.write(check(Integer.parseInt(st2.nextToken())) + " ");
        }
 
        bw.flush();
        bw.close();
    }
 
    public static int check(int num) {
        int cnt = 0;
 
        for (int i = 0; i < iArr.length; i++) {
            if (iArr[i] == num) {
                cnt++;
            }
        }
 
        return cnt;
 
    }
}
 

🚨 이중 for문에 의해서 시간복잡도가 n^2까지 커질 수 있어 시간 초과

- int[]

    - 정적 변수로 선언해서 main()과 check()이 공유

    - 초기값이 0이므로 따로 기본값 설정 X

 

😮 찾아본 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
 
    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());
 
        Map<Integer, Integer> map = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            int key = Integer.parseInt(st.nextToken());
 
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
 
        int M = Integer.parseInt(br.readLine());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
 
            bw.write(map.getOrDefault(key, 0) + " ");
        }
 
        bw.flush();
        bw.close();
    }
 
}
 

1. HashMap

    - 시간복잡도가 1로 검색 속도가 빠름

    - getOrDefault(): value값을 찾거나 초기값 선언

      ⭐ map은 key값이 중복되지 않음

        - key값이 없을 경우, 0 입력

        - key값이 있을 경우, get(key) + 1

2. getOrDefault()

    - 입력값마다 value 검색 후, 없을 경우 초기값을 0으로 설정

  ⭐ 1개의 map에는 상근이가 갖고 있는 카드 및 상근이가 갖고 있는지 확인 할 카드가 함께 저장되어 있음

 

 

 

🔗 소스 코드
HJ0216/TIL/BOJ

 

📚 참고 자료

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]