백준 문제 풀이 : 수 찾기 (1920)

재도전필요!⭐️

 

나의 문제 풀이 방법

처음에는 너무나 당연하게도 이중 for문 사용하려고 했는데, 입력 값 범위를 보니 10만x10이면 백억으로 시간 초과되잖아? 라는 생각에 어떻게 풀어야할지 너무 막막했다.

정렬도 해보고, 단일 for문 돌려봤지만 해답을 모르겠어서 결국 구글링!

 

문제 풀이 방법

해답은 '이분 탐색(Binary Search)' 이었다. 이분 탐색은 정렬되어있는 리스트에서 범위를 절반씩 줄여가며 탐색하는 알고리즘!

start, end, mid 카운터를 사용한다! 해당 알고리즘은 다시한번 공부하기!

 

풀이

const n = Number(input[0]);
const nArr = input[1].split(' ').sort();
const m = Number(input[2]);
const mArr = input[3].split(' ');

const asnwer = [];

mArr.forEach( item => {
    let start = 0;
    let end = n-1;
    let isAvailbe = false;
    
    while( start <= end) {
        let mid = parseInt((start+end)/2);
        if( item < nArr[mid]) {
            end = mid - 1;
        } else if ( item > nArr[mid] ) {
            start = mid + 1;
        } else {
            // 동일
            isAvailbe = true;
            break;
        }
    }
    if(isAvailbe) asnwer.push(1);
    else asnwer.push(0); 
})

console.log(asnwer.join('\n'));

 

링크

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