[백준] no10816: 숫자 카드 2

문제

: N개의 숫자 중 M개의 숫자와 동일 한 숫자 몇개인지 카운트하기

 

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

---

원리

1. 이분탐색(레퍼런스) : 링크 참고 https://st-lab.tistory.com/267

2. HashMap을 이용한 반복(내 방법)

 

---

나의 코드

1. 이중포문 (시간초과)

 1) M개의 수를 String배열로 만들고, 같은 길이의 int형 배열을 만듦

 2) N개의 수를 하나씩 뽑아 M개의 배열에 있는 수 중 일치하는 값이 있다면, int형 배열에서 같은 위치에 count

public class no10816 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        String[] strArr = new String[M];
        int[] countArr = new int[M];
        for(int i=0; i<M ; i++) strArr[i] = st2.nextToken();

        for(int i=0; i<N ; i++) {
            String temp = st.nextToken();
            for(int j=0; j<M ; j++) {
                if (temp.equals(strArr[j])) {
                    countArr[j]++;
                    break;
                }
            }
        }
        String result = "";
        for(int i=0; i<M ; i++) {
            result += countArr[i] + " ";
        }
        System.out.println(result);
    }
}

 

2. HashMap 사용 (StringBuilder에 append권장. String에 붙이면 시간 초과됨)

 1) N개의 수를 하나씩 뽑아 HashMap에 해당 String을 key 값으로 저장

 2) 뽑을때마다 Key값으로 존재한다면 +1, 없으면 새로저장

 3) M개의 수를 String으로 뽑아, 만약 일치하는 Key값이 HashMap에 있다면, 그 밸류값을 StringBuilder에 append

 4) M개의 수를 String으로 뽑아, 만약 일치하는 Key값이 HashMap에 없다면, 0을 StringBuilder에 append

public class no10816 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        HashMap<String, Integer> hm = new HashMap<>();
        for(int i = 0; i < N; i++) {
            String str = st.nextToken();
            if(hm.containsKey(str)) hm.put(str , hm.get(str)+1);
            else hm.put(str, 1);
        }

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<M ; i++) {
            String temp = st2.nextToken();
            if(hm.containsKey(temp)) sb.append(hm.get(temp) + " ");
            else sb.append("0 ");
        }

        System.out.println(sb);
    }
}

 

---

레퍼런스 코드

: 이분 탐색

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int[] arr = new int[N];

        for(int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);	// 이분 탐색을 하기 위해서 정렬.

        int M = in.nextInt();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < M; i++) {
            int target = in.nextInt();
            sb.append(upperBound(arr, target) - lowerBound(arr, target)).append(' ');
        }
        System.out.println(sb);
    }
    private static int lowerBound(int[] arr, int target) {
        int low = 0;
        int high = arr.length;

        while (low < high) {
            int mid = (low + high) / 2;
            if (target <= arr[mid]) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
    private static int upperBound(int[] arr, int target) {
        int low = 0;
        int high = arr.length;

        while (low < high) {
            int mid = (low + high) / 2;
            if (target < arr[mid]) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
}

 

참고 링크(코드) : https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-10816%EB%B2%88-java

참고 링크(이분탐색) : https://st-lab.tistory.com/267