99클럽 코테 스터디 13일차 TIL , 숫자 카드

 

문제

풀이

숫자 카드뭉치를 준다.

다른 숫자 뭉치를 주고 해당 값이 숫자 카드뭉치에 있는지 확인하는 문제이다.

당연히 그냥 for문 돌려서 확인하는 것이면 시간초과가 난다.

이분탐색으로 풀면 된다.

제출 - 정답

import java.util.*;
import java.io.*;
public class Main {
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] nArr = new int[n];
    
        StringTokenizer cards = new StringTokenizer(br.readLine());
        for(int i=0; i<n;i++){
            nArr[i]=Integer.parseInt(cards.nextToken());
        }

        Arrays.sort(nArr);

        int m = Integer.parseInt(br.readLine());
        StringTokenizer is = new StringTokenizer(br.readLine());
          
        StringBuilder answer = new StringBuilder();

        for(int i=0; i<m;i++){
            int isIn  = Integer.parseInt(is.nextToken());
            answer.append(sol(isIn, nArr)+" ");
        }
        
        System.out.println(answer.toString().strip());
    }
    private static int sol(int isIn, int[] arr){
        int result = 0;
        int lt = 0;
        int rt = arr.length-1;
        
        
        while(rt>=lt){
            int center = (lt+rt)/2;
            if(arr[center]==isIn){
                result = 1;
                break;
            }else if(arr[center]>isIn){
                rt = center-1;
            }else {
                lt = center + 1;
            }
        }
        
        return result;

    }
    
}

 

문제를 풀 때 탭으로 키보드 없이 코딩하고 하느라 좀 복잡하게 되어있고 import도 뭉뚱그려 되어있다.

그래도 어렵진 않지만 이분탐색 구현 방법을 잊지 않았다는 것에 만족했다 ㅎ.ㅎ

TIL

• 이분탐색의 위대함을 알았다.