백준

[백준] 10816 숫자 카드 2_ JAVA

채니◟( ˘ ³˘)◞ 2023. 7. 11. 17:15

● 문제


● 풀이

 

이는 10815 숫자 카드와 비슷한 문제이다.

다른 점은 상근이의 숫자 카드에서 주어진 M개 중 그 수가 적혀있는 숫자 카드의 개수를 구하는 것이다.

 

 

첫번째 풀이

 

시간 초과를 방지 하기 위해 일단 이분 탐색을 사용하였고, 배열에 존재하는 수 일때 개수를 구하기 위해 for문을 돌렸는데, 아마 이곳에서 시간 초과가 난 것 같다.

 

import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();

        int m = in.nextInt();
        for (int i = 0; i < m; i++) {
            int k = in.nextInt();
            int count =0;
            if (binarySearch(arr, k) >= 0) {
                for(int num : arr){
                    if(num == k){
                        count++;
                    }
                }
                sb.append(count).append(' ');
            } else
                sb.append('0').append(' ');
        }
        System.out.println(sb);
    }

    private static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (key < arr[mid]) {
                right = mid - 1;
            } else if (key > arr[mid]) {
                left = mid + 1;
            } else
                return mid;
        }
        return  -1;
    }
}

 


 

출처 : https://st-lab.tistory.com/267

 

전 10815 숫자 카드 문제에서는 arr[mid] 값과 key 값이 동일하면 반환을 했었다.

 

하지만, 이번 문제의 경우 우리가 고려할 점은 '중복 원소의 개수'를 알아내는 것이다.

중복 원소의 왼쪽 끝 값과 오른쪽 끝 값을 각각 알아내는 것이다.

 

 

첫번째 문제 풀이 (이분 탐색)

import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
		Arrays.sort(arr);	// 이분 탐색을 하기 위해서는 반드시 정렬되어있어야 한다.
		
		int M = in.nextInt();
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < M; i++) {
			int key = in.nextInt();
 
			// upperBound와 lowerBound의 차이 값을 구한다.
			sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
		}
		System.out.println(sb);
	}
 
 
	private static int lowerBound(int[] arr, int key) {
		int lo = 0; 
		int hi = arr.length; 
 
		// lo가 hi랑 같아질 때 까지 반복
		while (lo < hi) {
 
			int mid = (lo + hi) / 2; // 중간위치를 구한다.
 
			/*
			 *  key 값이 중간 위치의 값보다 작거나 같을 경우
			 *  
			 *  (중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다.)
			 */
			if (key <= arr[mid]) {
				hi = mid;
			}
 
			else {
				lo = mid + 1;
			}
 
		}
 
		return lo;
	}
 
	private static int upperBound(int[] arr, int key) {
		int lo = 0; 
		int hi = arr.length; 
 
		// lo가 hi랑 같아질 때 까지 반복
		while (lo < hi) {
 
			int mid = (lo + hi) / 2; // 중간위치를 구한다.
 
			// key값이 중간 위치의 값보다 작을 경우
			if (key < arr[mid]) {
				hi = mid;
			}
			// 중복원소의 경우 else에서 처리된다.
			else {
				lo = mid + 1;
			}
 
		}
 
		return lo;
	}
	
}

 

 


 

두번째 문제 풀이 ( 해시맵)

 

import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

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

        int N = scanner.nextInt();
        scanner.nextLine();

        StringTokenizer st = new StringTokenizer(scanner.nextLine(), " ");

        for (int i = 0; i < N; i++) {
            int key = Integer.parseInt(st.nextToken());
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        int M = scanner.nextInt();
        scanner.nextLine();

        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(scanner.nextLine(), " ");
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            sb.append(map.getOrDefault(key, 0)).append(' ');
        }

        System.out.println(sb);
    }
}