코딩테스트 연습 스터디 진행중 입니다. ✍✍✍
Notion : https://www.notion.so/1c911ca6572e4513bd8ed091aa508d67

문제

https://www.acmicpc.net/problem/10816

[나의 풀이]

import java.util.Arrays;
import java.util.Scanner;

public class Try2 {    
    public static void main(String[] args) {

        Scanner stdIn = new Scanner(System.in);

        int N = stdIn.nextInt();
        int [] cardArray = new int[N];

       for (int i=0;i<N;i++){

             cardArray[i] = stdIn.nextInt();

         }
        
        Arrays.sort(cardArray);

         int M = stdIn.nextInt();
         int [] findArray = new int[M];
         for (int i=0;i<M;i++){

             findArray[i] = stdIn.nextInt();

         }

        for (int i : binary_search(cardArray, findArray)){

            System.out.print(i+" ");
        }
     
        
    }
        private static int [] binary_search(int [] cardArray, int [] findArray){

        int [] output = new int [findArray.length];

        for (int i=0;i<findArray.length;i++){  
                                              
            int pl = 0;                         
            int pc = cardArray.length/2;   
            int pr = cardArray.length-1;   

            while(findArray[i]!=cardArray[pc]){

                if(findArray[i]>cardArray[pc]){
                    pl = pc+1;
                    pc += (pr-pl)/2+1;
                }
                else{ 
                    pr = pc-1;
                    pc = pc-(pr-pl)/2-1;
                }

                if(pl > pc || pc > pr){
                    break;
                }

            }

            if ( 0<=pc && pc < cardArray.length && findArray[i]==cardArray[pc]){
                output[i] +=1;
                for (int m=pc-1; 0<=m;m--){
                    if (cardArray[m]==findArray[i]){
                        output[i] +=1;
                    }
                }
                for (int m=pc+1; m<=pr;m++){
                    if (cardArray[m]==findArray[i]){
                        output[i] +=1;
                    }
                }
            }
            
        }

        return output;
    }
}

[정답 풀이]

import java.util.Arrays;
import java.util.Scanner;
 
public class Correct_answer {
 
	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;
	}
	
}

나의 풀이는 이진 탐색을 사용했음에도 계속 시간초과가 났다. 그리하여 정답을 참고하였고 Upperbound와 Lowerbound 개념을 활용해서 푼 것을 확인할 수 있었다.