[99클럽 코테 스터디 14일차 TIL] 숫자 카드 2 - Java [자바][백준]

 

 

📜 문제 내용

 

🤔 과정

• 백준 - 숫자 카드 (링크) 
• 위의 문제의 코드에서 변형하면 안되나? -> 안됨

• 애초에 배열이나 list 순회를 하지 않고 HashMap을 활용해 값에 대한 갯수를 put  해놓고 판별 숫자(target)을 key로 하여 값에 대한 갯수(value) 값을 찾아오면 된다. 

 

✨ 최초 제출 답안 - 시간 초과⏱️

import java.io.*;
import java.util.*;

public class Main {
    public static int n,m,target, cnt;
    public static int[] cards;
    public static void checkCnt(int start, int end){
        for(int i=start;i<=end;i++){
            if(cards[i]==target) cnt++;
        }
    }

    public static void main(String[] ars) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<m;i++){
            int start = 0;
            int end = n - 1;
            cnt = 0;

            target = Integer.parseInt(st.nextToken());

            while(start <= end){
                int mid = (start + end) / 2;
                if(cards[mid] == target){
                    checkCnt(start, end);
                    sb.append(cnt + " ");
                    break;
                }

                if(cards[mid] > target){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }

                if(start > end){
                    sb.append(0 + " ");
                    break;
                }
            }
        }

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

 

• 숫자 카드 1 코드에서 그냥 cnt 만 세서 냈더니 당연히 시간 초과가 떴다. 
• 만약 같은 숫자가 500,000 개가 있다면, 500,000 ^ 2 번 for문을 돌아야하므로 1억이 넘게 되어 1초 시간 제한을 넘어버린다. 

 

✍️ 재제출 답안

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] ars) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        HashMap<Integer, Integer> hashMap = new HashMap<>();

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            int key = Integer.parseInt(st.nextToken());
            
            // hashMap의 key에 해당하는 value를 다음 값으로 넣어라
            // key와 맵핑된 value 값을 반환하고 없으면 기본값 0을 반환
            hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            int target = Integer.parseInt(st.nextToken());
            
            // target에 맵핑된 value 값을 반환하고, 없으면 0 반환 
            sb.append(hashMap.getOrDefault(target, 0)).append(" ");
        }

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

 

 

 

🔗 문제 링크

• 백준 - 숫자 카드 2 (링크)