[Java] BJ.10816 숫자 카드2

10816번: 숫자 카드 2

풀이 (이분 탐색)

단순하게 이분 탐색으로 풀어보려 했더니 중복된 숫자들이 있었다. 그래서 탐색을 할 정렬된 배열에서 찾고자 하는 수가 처음 등장하는 곳과 끝의 길이를 내면 되지 않을까 생각했다. 즉 하한(Lower Bound)값과 상한(Upper Bound)값을 찾으면 되는 것이다. 이분 탐색을 통해 처음 찾고자 하는 곳을 찾고 다시 한번 이분 탐색을 통해 찾고자 하는 값이 마지막으로 나오는 곳을 찾고 상한값에서 하한값을 빼면 되었다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[] card;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        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(upperBound(card, key) - lowerBound(card, key) + " ");
        }
        bw.flush();
        bw.close();
    }

    static int lowerBound(int [] arr, int key){
        int lo = 0;
        int hi = arr.length;

        while (lo < hi){
            int mid = (lo + hi) / 2;

            if (key <= arr[mid]){
                hi = mid;
            }
            else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    static int upperBound(int [] arr, int key){
        int lo = 0;
        int hi = arr.length;

        while (lo < hi) {
            int mid = (lo + hi) / 2;

            if (key < arr[mid]) {
                hi = mid;
            }
            else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

 

풀이 (Counting Sort)

이분탐색 문제이기 때문에 Counting Sort도 가능하지 않을까 해서 문제를 풀어보았다. 다만 항상 Counting 정렬을 할 때에는 주의해야할 점이 있다. 입력 범위만큼의 공간을 차지하기 때문에 메모리 사용 측면에서 주의해야 한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int [] counting = new int[20000001]; // 수의 범위 -10,000,000 ~ 10,000,000
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            counting[Integer.parseInt(st.nextToken()) + 10000000]++;
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            bw.write(counting[Integer.parseInt(st.nextToken()) + 10000000] + " ");
        }
        bw.flush();
        bw.close();
    }
}

 

풀이 (HashMap)

이분 탐색이 아닌 HashMap을 사용한 풀이이다. 이분 탐색보다 빠르지만, 자료구조까지 구현해야하는 상황이라면 코드 작성에 상당한 시간이 걸리므로 주의해야 한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> hm = new HashMap<>();
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            int key = Integer.parseInt(st.nextToken());

            hm.put(key, hm.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(hm.getOrDefault(key, 0) + " ");
        }
        bw.flush();
        bw.close();
    }
}

 

위에서 부터

이분탐색

Counting Sort

HashMap 사용

풀이이다. 이분탐색 대비 Counting Sort, HashMap 모두 실행 속도는 빠르지만 Counting Sort는 확실히 메모리 사용량이 큰 것을 알 수 있다. 문제 제한 조건에 따라서 다양하게 풀 수 있도록 고려해볼 필요가 있다고 생각이 들었다.