[취업준비일지] - 107

오늘은 전반적인 우분투 20.04 -> 22.04 마이그레이션 및 추가적인 리눅스 기능확인 설치 등을 진행했다...

 

(1).백준 1920번 수 찾기는 특정 배열에 숫자가 포함되어 있는지를 묻는 문제였다.
중복이 없는 문제였는데 이분탐색을 하길 바라는 문제였다.

처음에는 그래도 될까 싶어서 includes를 사용했는데
역시나 시간초과로 터져버렸고

이진탐색을 구현한 다음 문제를 해결하려고 했으나
이상하게 제대로 처리가 되지 않았다.

반례들을 여러가지 넣어봐도 다 잘 되는데
왜 내 코드만 동작하지 않는지 살펴보다가
화가 나서 테스트케이스에 마구 집어넣었더니
갑작스럽게 오답이 나와버렸다.

뭐가 문제인지 확인하니 sort를 사용할 때
(a,b) => a-b를 사용하지 않고 기본 sort()만 사용했기 때문에
숫자의 오름차순 정렬이 아닌
문자열마냥 1,10,2,3,4,5와 같은 형태로 정렬되어 버린 것이었다.

이진탐색이니 당연히 오름 또는 내림차순의 정렬된 함수가 필요했기 때문에
답이 나오는 것이 이상한 상황이었다.

이진탐색을 오랬만에 구현했기 때문에
이진탐색에 뭐가 문제가 있는지 생각만 해봤지
또 입력이 문제일줄은 몰랐는데
처리 과정을 각각 하나의 기능으로 쪼갠 다음 
각 처리 과정에서 생길 수 있는 문제에 대해 한번 더 생각하는 습관을 들여야 할 것 같다.

이런 상황이 있을 수 있기 때문에 TDD와 단일책임원칙이 있는 것 같기도 하다.

const input = `5
4 1 5 2 3 7 9 5 10
5
1 3 7 9 5`.split('\n')

const searchArr = input[1].split(' ').map(Number).sort((a,b) => a-b)
const wantToFind = input[3].split(' ').map(Number)
const result = []

const isNumberExist = (num) => {
    let left = 0
    let right = searchArr.length-1
    while(left <= right){
        const middle = Math.floor((left+right)/2)
        if(searchArr[middle] === num){
            return 1
        }
        else if(searchArr[middle] > num){
            right = middle - 1
        }
        else{
            left = middle + 1
        }
    }
    return 0
     
}

wantToFind.forEach(el => result.push(isNumberExist(el)))
console.log(result.join('\n'))