[java]숫자 카드 2 - 백준10816

문제



풀이

문제 해석을 하자면,

  • 상근이는 숫자 카드 N개를 가지고 있다.
  • 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하라.


풀이

  • HashMap 을 사용하는 풀이와 이진탐색을 사용한 풀이가 대표적이다.
    • 이진탐색의 경우 upperBound 에서 lowerBound 를 빼주면 중복 개수를 구할 수 있어서 값을 구할 수 있다. -> 조금 복잡
    • HashMap 의 경우 입력을 받을때 중복이면 해당 키값에++; 해주면 된다. -> 매우 간단



코드

//HashMap 풀이
public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    HashMap map = new HashMap();
    for (int i = 0; i < N; i++) {
        int num = Integer.parseInt(stk.nextToken());
        if(map.containsKey(num)) map.put(num, (int) map.get(num)+1);
        else map.put(num, 1);
    }
    //run
    int M = Integer.parseInt(br.readLine());
    stk = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < M; i++) {
        int num = Integer.parseInt(stk.nextToken());
        if(map.containsKey(num)) sb.append((int) map.get(num));
        else sb.append(0);
        sb.append(" ");
    }
    System.out.println(sb);
}

//이진탐색 풀이
static int N, M;
static int[] inArr = new int[500005];

public static int lower_bound(int target, int len) {
    int st = 0;
    int en = len;
    while(st < en) {
        int mid = (st+en)/2;
        if(inArr[mid] >= target) en = mid;
        else st = mid+1;
    }
    return st;
}
public static int upper_bound(int target, int len) {
    int st = 0;
    int en = len;
    while(st < en) {
        int mid = (st+en)/2;
        if(inArr[mid] > target) en = mid;
        else st = mid+1;
    }
    return st;
}
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine());
    N = Integer.parseInt(stk.nextToken());
    stk = new StringTokenizer(br.readLine(), " ");
    for(int i = 0 ; i<N;i++) inArr[i] = Integer.parseInt(stk.nextToken());
    stk = new StringTokenizer(br.readLine());
    M = Integer.parseInt(stk.nextToken());

    Arrays.sort(inArr, 0, N);

    stk = new StringTokenizer(br.readLine(), " ");
    StringBuilder sb = new StringBuilder();
    for(int i = 0 ; i<M; i++) {
        int target = Integer.parseInt(stk.nextToken());
        sb.append(upper_bound(target, N)-lower_bound(target, N)).append(" ");
    }
    System.out.println(sb);
}



느낀점

생략

댓글남기기

참고