[백준 10816] 숫자카드2 - JAVA[이중 for문, 이분탐색, 자료구조 : 해시맵, Counting] 기법

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 백준 10816번

"숫자카드" 구현 포스팅입니다.

 

 

10816번: 숫자 카드 2

 

이번 포스팅은 글 제목에서 나오듯이 4가지 기법으로 풀어보겠습니다.

 

문제는 이해는 쉽습니다.

두 개의 배열이 주어지는데 두번째 배열에 해당하는 값이 첫번쨰 배열에 몇개 있는지 출력하면 되는 문제입니다.

 

1. 이중 for문 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

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));
        int n = Integer.parseInt(br.readLine());
        String[] wordN = br.readLine().split(" ");
        int m = Integer.parseInt(br.readLine());
        String[] wordM = br.readLine().split(" ");

        for(int i=0; i< wordM.length; i++){
            int count = 0;
            for(int j=0; j<wordN.length; j++){
                if(wordM[i].equals(wordN[j])){
                    count++;
                }
            }
            System.out.print(count + " ");
        }
    }
}

두 개의 배열을 받고 이중 for으로 하나씩 비교해주면 하나의 값이 비교가 끝나면 count 변수를 출력해주는 방법입니다.

 

가장 쉬운 방법이라고 생각합니다.

 

2. 이분탐색

이분탐색을 구현하고 이분탐색으로 찾는 방법입니다.

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

public class Main{
    public static int getLowCount(int[] arr, int x){
        int lower = 0;
        int high = arr.length;

        while(lower < high){
            int mid = (lower + high) / 2; //중간위치
            if(x <= arr[mid]){
                high = mid;
            }else{
                lower = mid+1;
            }
        }
        return lower;
    }

    public static int getHighCount(int[] arr, int x){
        int lower = 0;
        int high = arr.length;
        while(lower < high){
            int mid = (lower + high) / 2;
            if(arr[mid] > x){
                high = mid;
            }else{
                lower = mid+1;
            }
        }
        return lower;
    }
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] wordN = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i =0; i<n; i++){
            wordN[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(wordN);
        int m = Integer.parseInt(br.readLine());
        StringTokenizer stM = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<m; i++){
            int x = Integer.parseInt(stM.nextToken());
            sb.append(getHighCount(wordN, x) - getLowCount(wordN, x)).append(' ');

        }
        System.out.println(sb);
    }
}

 

 

3. 자료구조 : 해시맵을 사용하는 방법입니다.

해시맵으로 푼 방법은 해당하는 키값이 있으면 value를 하나씩 추가해주는 방법으로 풀었습니다.

이 방법으로 풀기 위해서는 getOrDefalut메소드를 사용하면 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        /*
        HashMap<key, value>
        key = 입력되는 원소
        value = 원소의 개수(=중복 입력된 원소의 수)
        */
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int wordN[] = new int[n];
        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(), " ");
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<m; i++){
            int key = Integer.parseInt(st.nextToken());
            sb.append(map.getOrDefault(key,0)).append(' ');
        }
        System.out.println(sb);
    }
}

 

 

4. Counting기법

이 방법은 N의 갯수의 *2로 배열을 선언해줍니다. 두배로 한 이유는 -1도 있기 때문에

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static int[] countArr = new int[20000001];
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i<n; i++){
            int idx = Integer.parseInt(st.nextToken());
            countArr[idx+10000000]++;
        }

        int m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<m; i++){
            int arrIdx = Integer.parseInt(st.nextToken());
            sb.append(countArr[arrIdx+10000000]).append(' ');
        }
        System.out.println(sb);
    }
}

코드에서 보이듯이 해당하는 값이 있으면을 추가해서 배열값을 ++ 해줍니다. a배열기준으로

10000000

 

그 후에 b배열 기준으로 위에 이미지에 해당하는 인덱스의 값을 출력해주면 원하는 답이 나옵니다.

 

 

이런 간단한 문제에도 여러 방법이 있으니 알아가시는 게 좋을 거 같습니다.

 

감사합니다.