[1874] 수 찾기 Find number

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

My solution

이진탐색으로 문제를 푸는데 하나의 값을 찾는 것이 아니라 배열의 원소를 돌아가면서 하나씩 찾아서 0 또는 1을 넣어주어야 했다. while문이 중첩되어 시간복잡도가 O(n^2)가 되었는데 제출해보니 시간초과가 떴다.

(...)
   while (mArr.length) {
        let el = mArr.shift();
        while (lt <= rt) {
            mid = Math.floor((lt + rt) / 2);
            if (mArr.includes(nArr[mid])) {
                // nArr의 값이 mArr에 있다면?
                answer += "1\n";
                chk = 1;
                break;
            } else if (nArr[mid] > el) rt = mid - 1;
            else lt = mid + 1;
        }
        if (!chk) answer += "0\n";
    } // 시간 초과?
JavaScript
복사

for문으로 바꾸고 인덱스로 지정해서 비교 돌려보았더니 시간초과가 문제가 아니라 그냥 틀리는 것이다. 로직은 틀린 게 없는 거 같아서 변수쪽에서 살펴보았더니 정수문자열로 구성된 배열에 sort() 메서드를 호출한 것을 발견했다.

정수문자열인 경우 1~9까지 한자리 숫자는 상관 없지만 두자리 수 이상은 아스키코드로 사전순 비교하게 되어 제대로 정렬되지 않는 것을 확인해 변경했다.

소스코드

function solution(i) {
    const input = i.toString().trim().split("\n");
    [n, nArr, m, mArr] = input;
    nArr = nArr.split(" ").map((v) => parseInt(v));
    nArr.sort((a, b) => a - b); // 음수 문자열이 정수화되어야 제대로 sort된다.
    mArr = mArr.split(" "); //.map((v) => parseInt(v));
    let answer = "";

    console.log(nArr, mArr);

    for (let i = 0; i < mArr.length; i++) {
        let lt = 0;
        let rt = nArr.length - 1;
        let mid = -1;
        let chk = 0;
        while (lt <= rt) {
            mid = Math.floor((lt + rt) / 2);
            console.log(nArr[mid], mArr[i]);
            if (nArr[mid] == mArr[i]) {
                answer += "1\n";
                chk = 1;
                break;
            } else if (nArr[mid] > mArr[i]) rt = mid - 1;
            else lt = mid + 1;
        }
        if (!chk) answer += "0\n";
    }

    console.log(answer);
    // return answer; // 테스트용
}

test("solution", () => {
    expect(solution("5\n4 1 5 2 3\n5\n1 3 7 9 5")).toStrictEqual(
        "1\n1\n0\n0\n1\n"
    );
});
JavaScript
복사