백준 No.10816 숫자카드2- JAVA

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적있는 숫자 카드를 상근이가 몇개 가지고 있는지 구하는 프로그램을 작성하시오.

 

 

 

풀이

일단 처음 이진탐색으로 접근했는데 주어진 입력으로 풀었을 때는 답이 나왔는데 제출하고 나니 틀렸다. 

처음 접근했던 방법은 List를 통해 주어진 10개에 입력을 받고 이진탐색으로 찾는 숫자카드를 먼저 하나 찾으면 true를 리턴하고 N-1 한 다음 찾은 그 값을 remove를 통해 제거했다. 그러면 10개였던 배열이 9개가 되면서 N도 그에 맞게 9가 된다. 그 다음 한 번 찾았을 경우 다시 이진탐색을 해서 탐색을 시도해서 값이 없다면 해당 숫자로는 탐색을 멈춘다. 그렇게 탐색횟수를 카운트하여 StringBuilder에 추가해서 출력했는데 출력이 맞는 답이었다. 근데 시간복잡도 때문에 틀린 접근인 거 같았다. 두번째 입력부터는 큰 입력이 주어지는 거 같았다.

ㄱ근데 막상 생각해보니 입력을 받을 때부터 숫자 체크를 하면 더 쉬울 거 같았다. 해쉬 맵 쓰니까 너무 쉽게 풀렸지만 제출하고 보니 해쉬맵으로 제출 했는데도 체점이 상당히 느렸다. 그러니 당연히 반복적인 탐색은... 안 되는 거였다.

 

 

 

일단 이진 탐색으로 틀린 접근

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

public class Main {

    static ArrayList<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());


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

        Collections.sort(list);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < M; i++) {
            int temp  =0;
            int find = Integer.parseInt(st.nextToken());

            boolean result = true;
            while(result){

               result =  solution(find,N);

              if(result){
                  N--;
                  temp++;
              }
            }
            sb.append(temp).append(" ");

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

    }

    static boolean solution(int find, int N){
        int left = 0;
        int right = N -1;

        while(left <= right){
            int midIndex = (left+right)/2;
            int mid = list.get(midIndex);

            if(mid > find){
                right = midIndex - 1;
            }else if(mid < find){
                left = midIndex + 1;
            }else if(mid == find){
                list.remove(midIndex);
                return true;
            }
        }
        return false;
    }

}

 

 

해쉬맵으로 맞는 접근

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            if(hashMap.containsKey(num)){
                int temp = hashMap.get(num);
                temp++;
                hashMap.put(num,temp);
            }else{
                hashMap.put(num,1);
            }

        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M ; i++) {
            int temp = Integer.parseInt(st.nextToken());

           if(hashMap.containsKey(temp)){
                sb.append(hashMap.get(temp)).append(" ");
           }else{
               sb.append(0).append(" ");
           }
        }

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

    }
}