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

문제 출처

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

7795번: 먹을 것인가 먹힐 것인가

 

문제

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입력 1 복사

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

예제 출력 1 복사

7
1

문제 풀이 힌트 

이분 탐색을 활용해서 문제를 풀어보자! 

 

A = [8,1,7,3,1]

B = [3,6,1]

 

A 배열을 반복문 돌면서 각 요소를 a라고 하자. 

B 배열은 오름차순으로 정렬 하자 // [1,3,6]

 

예시) 

a = 8일 때, start = 0, end=2 

    mid = 1 

   B[mid] = 3 

a > B[mid] 이다.

재귀함수를 이용해서 start에 mid+1 값을 넣는다. 

 

그럼, 

start = 2 end = 2

mid = 2

B[mid] = 6 

a > B[mid] 이다. 

재귀함수를 이용해서 start에 mid+1 값을 넣는다. 

 

그럼 

start = 3, end=2

만약 start > end 일 때 return start를 해준다. 

즉, 8은 B 배열의 요소들 중 3개보다 크다 !! 

 

a = 1일 때, ...

a = 3일 때, 

a = 7일 때, ...

a = 1일 때, ...

문제 풀이 코드 1

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const tc = Number(input.shift())

function binarySearch(target, arr, start, end){
    while(start <= end){
          let mid = parseInt((start + end) / 2)
          if(arr[mid] < target){
              start = mid + 1
          }else{
              end = mid - 1
           }
         }
    return end+1
}

let answer = []; 
for(let i=0; i<tc; i++){
    let [n,m] = input.shift().split(' ').map(v => +v); 
    let arr1 = input.shift().split(' ').map(v => +v); 
    let arr2 = input.shift().split(' ').map(v => +v); 
    arr2.sort((a,b) =>a-b)
    
    let start = 0; 
    let end = arr2.length-1
    
    let cnt = 0; 
    
    for(let j=0; j<arr1.length; j++){
       cnt += binarySearch(arr1[j], arr2, start, end)
    }
    answer.push(cnt)
}

console.log(answer.join('\n'))

문제 풀이 코드 2

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const tc = Number(input.shift()); 
let answer = [];

function binarySearch(start, end, a, B){
    if(start > end) return start; //start가 end 보다 값이 커질 때 start 값 === a가 B 배열 요소보다 큰 개수
    const mid = Math.floor((start + end) / 2); 
    
    if(B[mid] < a){ //아직 a보다 작을 때 
        return binarySearch(mid+1, end, a, B) //start 값을 mid +1로. 
    }else {
        return binarySearch(start, mid-1, a, B) //end 값을 mid -1로.
    }
}

for(let i=0; i<tc; i++){
    const [M,N] = input.shift().split(' ').map(v => +v); 
    const A = input.shift().split(' ').map(v => +v); 
    const B = input.shift().split(' ').map(v => +v).sort((a,b) => a-b); //B는 오름차순 정렬
    
    const startIdx = 0; 
    const endIdx = N-1; 
    let count = 0; 
    
    for(const a of A){//A를 반복문 돌면서 각 요소를 a라고 지정 
        count += binarySearch(startIdx, endIdx, a, B) //a가 b보다 큰게 몇갠지 
    }
    answer.push(count); 
}
console.log(answer.join('\n'))

알고가는 ppoint

아니,  solution(a, B, mid+1, end) 이 부분앞에 왜 return을 써줘야해?

solution(a, B, mid+1, end) 앞에 return을 사용해야 하는 이유는 다음과 같습니다.

1. 함수 정의 위반:

solution 함수는 정수를 반환하도록 정의되어 있습니다. 하지만 return을 사용하지 않으면 함수 정의를 위반하여 예상치 못한 동작을 초래할 수 있습니다.

2. 코드 가독성 저하:

return을 사용하지 않으면 코드를 읽고 이해하기 어려워집니다. 각 조건문에서 명확하게 return 값을 지정하는 것이 코드의 가독성을 높이고 의도를 명확하게 전달합니다.

3. 오류 가능성 증가:

return을 사용하지 않으면 특정 조건에서 값을 반환하지 않아 오류가 발생할 가능성이 높아집니다. 모든 조건에서 명확하게 return 값을 지정하여 오류를 방지하고 코드의 안정성을 높일 수 있습니다.

4. 현재 코드의 동작:

현재 코드에서는 solution(a, B, mid+1, end) 앞에 return을 사용하지 않기 때문에 함수는 아무것도 반환하지 않습니다. 따라서 count 변수에 값이 누적되지 않고 최종 결과가 항상 0이 될 것입니다.

5. 올바른 코드:

solution(a, B, mid+1, end) 앞에 return을 추가하면 함수는 mid+1 값을 반환하게 됩니다. 이는 a가 B의 mid+1 위치에 삽입되어야 한다는 것을 의미합니다. 이렇게 하여 count 변수에 올바른 값이 누적되고 최종 결과가 정확하게 계산됩니다.

6. 추가 설명:

• 만약 모든 조건문에서 동일한 값을 반환해야 하는 경우, 함수 처음에 return 값을 지정하여 간결하게 작성할 수 있습니다.
• 예외적으로, 특정 조건에서만 값을 반환하고 싶은 경우, return을 사용하지 않고 함수 내 변수를 조작하여 결과를 반환할 수 있습니다. 하지만 이 경우 코드의 가독성이 떨어질 수 있으므로 주의해야 합니다.

결론:

일반적으로 함수 정의에 명시된 반환 값을 따르고 각 조건문에서 명확하게 return 값을 지정하는 것이 코드의 정확성, 가독성, 안정성을 높이는 가장 좋은 방법입니다.

 

02. 틀린 풀이 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const tc = Number(input.shift()); 
 function binarySearch(a, B, start, end){
      const mid =(start + end)/2 
    while(start <= end){
           if(B[mid] > a){
           return binarySearch(a, B, start, mid-1); 
     }else{
         return binarySearch(a, B, mid+1, end); 
     }
  }
          return start; 
 }
let answer = 0; 
for(let i=0; i<tc; i++){
   const [M,N] = input.shift().split(' ').map(v => +v); 
       let A = input.shift().split(' ').map(v => +v); 
       let B = input.shift().split(' ').map(v => +v).sort((a,b) => a-b); 
    for(let a of A){
        let start = 0; 
        let end = B.length; 
       answer += binarySearch(a, B, start, end); 
    }
}

console.log(answer);

수정한 코드) 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const tc = Number(input.shift()); 
 function binarySearch(a, B, start, end){
      const mid = Math.floor((start + end)/2) 
    while(start <= end){
           if(B[mid] < a){
           return binarySearch(a, B, mid+1, end); 
     }else{
         return binarySearch(a, B, start, mid-1); 
     }
  }
          return start; 
 }

let answer = []; 
for(let i=0; i<tc; i++){
   const [M,N] = input.shift().split(' ').map(v => +v); 
       let A = input.shift().split(' ').map(v => +v); 
       let B = input.shift().split(' ').map(v => +v).sort((a,b) => a-b); 
        let count = 0; 
    for(let a of A){
        let start = 0; 
        let end = B.length-1; //B.length 로 틀리게 작성 
       count += binarySearch(a, B, start, end); 
    }
    answer.push(count)
}

console.log(answer.join('\n')); //