<백준> 10816번 자바 알고리즘 [이분탐색]

 

아래는 이분탐색에 대해 생각 안하고 접근하다가

시간 초과로 틀린 코드다 

예제에 대한 답은 맞다 

import java.util.*;


public class Main
{
    static int N, M;
    static HashMap<Integer, Integer> hashMap;
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        hashMap = new HashMap<Integer, Integer>();
        
        for(int i = 0; i< N; i++){
            int n = in.nextInt();
            if(hashMap.get(n) == null){ // 처음 넣을 때 
                hashMap.put(n, 1);
            }else { // 두번째 부터 
                hashMap.put(n, hashMap.get(n) + 1); // n : 이전 value + 1
            }
        }
        
        M = in.nextInt();
        for(int j=0; j < M; j++){
            int m = in.nextInt();
            numberCheck(m);
        }
        
	}
	private static void numberCheck(int m){
	    if(hashMap.get(m) != null){
	        System.out.print(hashMap.get(m) + " ");
	    }else {
	        System.out.print(0 + " ");
	    }
	}
}

가지고 있는 숫자 카드 = N

M => 몇개를 상근이가 가지고 있는지 알아야 됨 

HashMap 으로 숫자마다 몇개 가지고 있는지 구현해볼까


함수에 숫자 파라미터로 전달해주면서 
몇개인지 알면 되지 않을까 

 

 

N 입력받기
for(N):
    만약 hashMap 처음 넣을때, 이후에 중복해서 넣을 때 구분해서 코드 입력하자

---

 

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);
		
		int M = in.nextInt();
		
		StringBuilder sb = new StringBuilder();
		
		for(int j = 0; j < M; j++){
		    int key = in.nextInt();
		    
		    sb.append(high(key, arr) - lower(key, arr) + " ");
		    
		}
		
		System.out.println(sb);
		
		
	}
	
	private static int lower(int key, int[] arr){
	    int lo = 0;
	    int hi = arr.length;
	    
	    while(lo < hi){
	        int mid = (lo + hi) / 2;
	        
	        if(key <= arr[mid]){
	            hi = mid;
	        }
	        else {
	            lo = mid + 1;
	        }
	    }
	    return lo;
	}
	private static int high(int key, int[] arr){
	    int lo = 0;
	    int hi = arr.length;
	    
	    while(lo < hi){
	        int mid = (lo + hi) / 2;
	        
	        if(key < arr[mid]){
	            hi = mid;
	        }
	        else {
	            lo = mid + 1;
	        }
	    }
	    return hi;
	}
}

num 1 2 3 4 4 4 5 7 9
idx 0 1 2 3 4 5 6 7 8

mid = 4 

idx 개수 9개 


ex) 4의 중복갯수 구하려면

4의 첫번째와 마지막의 거리를 구하면 됨 

lower higher

로 나눠서 두 거리를 빼자 


먼저 lower)
중복된 4의 인덱스 첫번 째에 위치 하도록 해야 한다

일단 key와 비교하면서 찾아 나서야겠다

if mid 가 key 랑 같을 때)
hi = mid
=> mid = 2 가 되겠다 
if mid 가 key 보다 작을 때)
lo = mid + 1
=> lo = 3 hi = 4
=> hi = 3 가 되므로 lo 와 hi 가 똑같음 => return 하자

 

high는 반대로 하면 된다 
즉 mid 가 key 랑 같을 때 => lo = mid + 1