baekjoon. 수 찾기

문제

링크

1920번: 수 찾기

 

풀이

얼핏 보기에 굉장히 쉬워보여서 내장 메서드만 사용해서 풀었는데 시간 초과

시간 복잡도를 줄이기 위해서 배열에 M이 있는지 여부를 확인하기 위해 이분 탐색을 이용하려했다

이분 탐색을 사용하기 위해서는배열이 정렬되어있어야 하기 때문에 배열을 정렬해주고 코드를 짜서 돌렸더니 계속 실패...

이분 탐색 구현이 잘못되었나 싶어서 여기저기 뜯어봐도 문제가 없었다

결국 다른 사람의 풀이를 보았는데도 딱히 문제가 되는 점을 찾지 못했다

문제는 전혀 엉뚱한 곳인 배열을 정렬해주는 부분에 있었다 내장 메서드인 sort를 사용할 때 compare함수를 명시해주지 않은 것

문자열 비교외의 정수 비교에서는 compare함수를 정의해주지 않아도 되는 줄 알았는데 그게 아니었다

sort메서드에 대해서는 한 번 포스팅을 했었는데도 불구하고 이런 부분에서 틀리다니 조금 자괴감이 들었고 앞으로는 sort를 쓸 때 어느 상황에서든 명시해주어야겠다

코드

    function solution(input){
        let answer = '';
        input = input.split('\n').map(v=>v.split(' ').map(v=>v*1));

        const arr = input[1].sort((a, b) => a-b);
        const numbers = input[3];

        numbers.forEach(v=>{
            if(binarySearch(arr,v)) answer += 1+'\n';
            else answer+=0+'\n';
        });
        console.log(answer.trim());
    }
    function binarySearch(arr, target){
        let start = 0;
        let end = arr.length-1;

        while (start<=end){
            const mid = Math.floor((start+end)/2);

            if(arr[mid]===target) return true;

            if(arr[mid] > target){
                end = mid-1;
            }else start = mid+1;
        }
        return false;
    }

다른 풀이

이 다음 단계인 숫자 카드2 문제를 풀면서 이 문제도 맵 자료구조를 이용해서 풀 수 없을까 생각이 들어서 다시 풀어봤다

'이분 탐색 문제니까 이분 탐색으로 풀어야지!' 라는 생각 때문에 다른 방법을 떠올릴 생각도 하지 않았다

실제 코딩테스트에서는 어떤 방법으로 풀어야하는지 가르쳐주지 않으니까 조금 걱정된다.. 많이 풀어서 많은 유형을 익혀야겠다

    function solution(input){
        input = input.split('\n').map(v=>v.split(' ').map(v=>v*1));
        let answer = '';
        const map = new Map();

        input[1].forEach(number=>{
            map.set(number, 1);
        });

        input[3].forEach(number=>{
            if(map.has(number)) answer += 1+'\n';
            else answer += 0+'\n';
        });

        console.log(answer.trim());
    }