https://www.acmicpc.net/problem/1920
const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim()
const solution = (input) => {
const [a,b,c,d] = input.split('\n')
return d.split(' ').map(v => {
let n = b.split(' ').sort((a,b)=>a-b)
while(true){
let mid = parseInt(n.length/2)
if(n.length === 0){
return 0
}else if(v === n[mid]){
return 1
}else if(+v < +n[mid]){
n = n.slice(0, mid)
}else if(+v > +n[mid]){
n = n.slice(mid+1)
}
}
}).join('\n')
}
console.log(solution(input))
다음과 같은 테스트 케이스에서
const input = `5
4 1 5 2 3 11 10 12 9
5
1 3 7 9 5 2 4`
이분 탐색에 대해 나름 이해한대로 구현해보았다. v
와 n[mid]
를 비교하는데 7 > 11
이라는 오류가 발생해서 뭐지?? 하고 콘솔도 찍어보고 한참 들여다봤다. 알고보니 string타입이라서 유니코드 문자를 기준으로 비교한 결과였다는ㅋㅋ +
기호를 덧붙여서 number타입으로 변환하여 이 부분은 해결했지만 시간 초과 이슈가 여전히 있었다.
slice를 썼기 때문일까?
slice는 기존 배열에서 얕은 복사로 새 배열을 반환한다.
const solution = (input) => {
const [a,b,c,d] = input.split('\n')
let n = b.split(' ').map(Number)
let m = d.split(' ').map(Number)
n.sort((a,b)=>a-b);
return m.map(v => {
let [s, e] = [0, n.length-1]
while (s <= e){
let mid = parseInt((s + e)/2)
if (v < n[mid]) {
e = mid - 1;
}else if (v > n[mid]){
s = mid + 1;
}else{
return 1
}
}
return 0
}).join('\n')
}
시간초과 부분을 해결하기위해 구글링으로 찾은 참고자료를 조금 어레인지했다.
시작s
과 끝e
의 index를 정의하여 while문의 조건식에 변화를 주었다.
배열객체의 복사 없이 기존 배열의 index값만 다르게 접근해서 그런지 시간초과 이슈 없이 통과했다.
참고 자료
const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim()
const solution = (input) => {
const [a,b,c,d] = input.split('\n')
const n = b.split(' ').map(Number)
const m = d.split(' ').map(Number)
const arr = new Set(n)
return m.map(v=>arr.has(v) ? 1 : 0).join('\n')
}
console.log(solution(input))
Set을 사용하면 자동정렬을 해줄뿐 아니라 has()메소드를 이용해 객체에 요소가 존재하는지 여부를 알 수 있었다.
참고 자료