문제 링크
https://www.acmicpc.net/problem/1920
구현
<첫 답안>
const fs = require('fs');
const input = fs.readFileSync('예제.txt', 'utf8').trim().split('\n'); // 백준 경로:'/dev/stdin'
const N = parseInt(input[0]);
const arrayA = input[1].split(' ').map(Number).sort((a,b)=> a-b);
const M = parseInt(input[2]);
const arrayB = input[3].split(' ').map(Number);
const result = [];
//B의 수가 A에 존재하면 1, 아니면 0
//binary search
let start = 0;
let end = N-1;
for(const target of arrayB){
while(start<=end){ //루프 종료 조건 : 시작인덱스>종료인덱스
let mid = Math.floor((start + end)/2);
let midValue = arrayA[mid];
if(midValue>target){
end = mid - 1;
}
else if(midValue<target){
start = mid + 1;
}
else if(midValue === target){ //반복문 종료
result.push(1);
break;
}
else { //못찾았을때
result.push(0);
}
}
}
console.log(result);
<문제점>
- start, end, found 를 각 target마다 초기화해야한다.
- target값이 없을 때 로직을 잘못 구현했다.
else { //못찾았을때
result.push(0);
}
while 문에서 이 코드는 절대 실행되지 않는다.
target 값이 없으면 인덱스가 조정되어 while 루프가 끝날 뿐, else에 도달하지 않는다.
따라서 while문이 끝난 뒤 찾지 못한 사실을 확인하고, 0을 추가해야한다.
<올바른 답안>
const fs = require('fs');
const input = fs.readFileSync('예제.txt', 'utf8').trim().split('\n'); // 백준 경로:'/dev/stdin'
const N = parseInt(input[0]);
const arrayA = input[1]
.split(' ')
.map(Number)
.sort((a, b) => a - b);
const M = parseInt(input[2]);
const arrayB = input[3].split(' ').map(Number);
const result = [];
//B의 수가 A에 존재하면 1, 아니면 0
//binary search
for (const target of arrayB) {
let start = 0;
let end = N - 1;
let found = false;
while (start <= end) {
//루프 종료 조건 : 시작인덱스>종료인덱스
let mid = Math.floor((start + end) / 2);
let midValue = arrayA[mid];
if (midValue > target) {
end = mid - 1;
} else if (midValue < target) {
start = mid + 1;
} else {
//midValue === target
result.push(1);
found = true;
break;
}
}
if (!found) {
result.push(0);
}
}
console.log(result.join('\n'));
'알고리즘 > 탐색' 카테고리의 다른 글
| [프로그래머스] Lv 2. 게임 맵 최단 거리 - Javascript 풀이 (1) | 2025.02.04 |
|---|---|
| [프로그래머스] Lv 2. 타켓 넘버 - Javascript 풀이 (1) | 2025.01.30 |