백준7795 - 먹을 것인가 먹힐 것인가 (이분탐색) JS

https://www.acmicpc.net/problem/7795

문제는 다음과 같이 A의 요소 값 > B의 요소 값을 만족하는 모든 경우를 출력하는 문제다.

수의 길이가 각각 '2만' 이하이기 때문에 완전탐색으로는 해결할 수 없으니, 이분탐색으로 해결했다.

 

이분탐색은 넓게 보아 탐색 범위를 좁혀가며 값을 찾아내는 방법이다.

위에 주어진 첫 번째 예시로, A = [1,3,7] 이고, B = [1,3]이라고 두자.

그리고 두 배열의 이분탐색 과정을 글로 쓰면 다음과 같다.

1. A[0] = 1과 B[0] = 1 을 비교했을 때, A의 요소 값 > B의 요소 값을 만족하지 못한다.

2. A[1] = 3과 B[0] = 1 을 비교했을 때, A의 요소 값 > B의 요소 값을 만족한다.
  => 이때, A,B는 오름차순으로 정렬된 배열이므로 A[1] 이후 값들은 모두 B[0]보다 크다.
  => 따라서 A[1] 이후부터는 B[1]부터 비교할 수 있다. (B의 인덱스 + 1(0 + 1) 을 기록한다.) 
  => 이분탐색의 범위를 줄이는 과정
  
3. A[1] = 3과 B[1] = 3 을 비교했을 때, A의 요소 값 > B의 요소 값을 만족하지 못한다.
  => B의 인덱스를 결괏값에 합산
  
4. A[2] = 7과 B[1] = 3 을 비교했을 때, A의 요소 값 > B의 요소 값을 만족한다.
  => 기록해두었던 B의 인덱스인 1을 가져와서 B[1]부터 비교한다.
  => A[2] = 7 > B[1] = 3 이므로, (B의 인덱스 = 2 를 기록한다.) 
  => B의 모든 수를 순회하였으므로 결괏값에 B의 인덱스를 합산 후 종료

 

 

 

그리고 위 과정을 코드로 옮기면 다음과 같다.

const binarySearch = (arr) => {
  // 각각의 배열로 정렬
  const [aArr,bArr] = arr.map(el => el.split(' ').map(Number).sort((x,y)=> x-y))
  
  // 전쳇값, B의 인덱스 선언
  let [sum,idx] = [0,0]
  
  aArr.forEach(a => {
  // a의 요소가 배열B[b의 인덱스]보다 크며, b의 인덱스가 배열B의 길이를 초과하지 않은 경우,
    while(a > bArr[idx] && idx < bArr.length) {
    // b의 인덱스를 증가시킨다.
      idx ++
    }
    // 루프가 끝날 시 결괏값에 합산
    sum += idx
  })
  return sum
}

 

전체 소스 코드

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

const binarySearch = (arr) => {
  const [aArr,bArr] = arr.map(el => el.split(' ').map(Number).sort((x,y)=> x-y))
  let [sum,idx] = [0,0]
  
  aArr.forEach(a => {

    while(a > bArr[idx] && idx < bArr.length) {
      idx ++
    }
    sum += idx
  })
  return sum
}

function solution(data) {
  data.shift()

  const testCases = []
  data.forEach((_, idx)=> {
    if(idx % 3 === 0) testCases.push([data[idx + 1], data[idx + 2]])  
  })

  const result = testCases.map(el => binarySearch(el))
  console.log(result.join('\n'))
}

solution(input)