백준 1744: 수 묶기 - javascript(그리디)

문제 출처 

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

 

문제 풀이

머리 뽀갈 날뻔 했다.

그래도 1시간 30분 걸려서 풀어냈다..   

 

역시 test case를 추가하면서 어떤 부분을 놓쳤는지 알아내는 것이 참 중요하다 

처음에 작성한 코드는 웬만하면 틀린 부분이 있기 때문에,  

console.log() 를 잘 이용해서 자신의 실수를 잘 발견하는 것이 코테의 핵심이라는 생각이 든다. 

 

거두절미하고, 

이 문제의 핵심은 뭐다?

"어떻게 묶어야 최대의 값이 될까?"

 

내가 세운 기준은 이렇다. 

 

- 1. 절대값이 큰 숫자대로 곱한다. 

- 2. 양수끼리 계산하고, 음수끼리 계산한다. 

- 3.양수끼리 계산할 때 1은 묶지 말고 더해준다. 

- 4. 음수끼리 계산할 때 0이 있다면 묶어준다. 

 

이제 이 부분에 대해서 이야기 해보려고 한다. 

 

## 1. 절대값이 큰 숫자대로 곱한다.

[1,2,5,7]

이 배열일 경우에 어떻게 묶는 것이 제일 큰 값이 될까? 

 

(1 * 2) +  (5 * 7) = 37

(1 * 5) +  (2 * 7) = 19

(1 * 7) +  (2 * 5) = 17

 

큰 순서대로 곱해준 값이 제일 크다. 

## 2. 양수끼리 계산하고, 음수끼리 계산한다. 

 

음수끼리 곱하면 양수가 된다. 그러니 양수랑 음수로 나눠주자. 

 

그러면 0은 어떻게 해야할까? 

- 양수배열로 들어가는 것이 이득일까?

- 음수배열로 들어가는 것이 이득일까?

 

결론부터 말하면 음수배열이다. 그건 아래 4번에서 납득이 갈 수 있다. 

## 3.양수끼리 계산할 때 1은 묶지 말고 더해준다. 

[6,4,1,1]

이 경우에 1은 묶지 않는 것이 이득이다. 

- 1은 묶어서 곱해봤자 아무 도움이 안되지만

- 안묶여서 더하기라도 하면 그래,,, 1이라도 도움된다. 

 

- (6* 4) + (1 * 1) = 25

- (6* 4) + 1 + 1 = 26

## 4. 음수끼리 계산할 때 0이 있다면 묶어준다. 

[-6,-5,-4,0] 이 경우를 살펴보자. 

- 절대값이 큰 순서대로 곱하기로 했으니 곱해보자 

(-6 * -5) + (-4 * 0) = 30

 

오 좋다. 0이 있다면 주저하지 말고 음수배열에 넣어서 음수랑 곱해주자. 

 

이 아이디어로 코드를 직접 작성해보면 좋겠다 ! 

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const N = Number(input.shift()); 
const arr = []; 
for(let i=0; i<N; i++){
    arr.push(Number(input[i]))
}
function solution(arr, N){
    arr.sort((a,b) => b-a)
    let idx = binarySearch(arr, 0)
    let pos = arr.slice(0, idx)
    let neg = arr.slice(idx)
    let pos_total = calPos(pos)
    let neg_total = calNeg(neg)
    return pos_total + neg_total 
    
    //배열을 넘겨받으면 묶어서 더한다. 
    //양수 배열, 
    //1은 곱하는 것보다 더하는 것이 좋음. 
    function calPos(arr){
        let total = 0; 
        arr.sort((a,b) => b-a)
        let one_idx = binarySearch(arr, 1)
        let new_arr = arr.slice(0, one_idx); 
        let one_arr = arr.slice(one_idx)
        let n = new_arr.length; 
        if(n === 1) total += new_arr[0]
        else{
            if(n %2 === 0){
             for(let i=0; i<=n-2; i+=2){
              total += (new_arr[i] * new_arr[i+1])
          }    
        }else{
            for(let i=0; i<=n-3; i+=2){
               total += (new_arr[i] * new_arr[i+1])
            }
            total += new_arr[n-1]
        }
        }
        if(one_arr.length >=1){
             total += one_arr.reduce((a,b) => a+b) 
        }
        return total 
    }
    
    
    //음수 배열, 
    //- -끼리는 곱하면 양수가 된다. 
    //- 만약 0이 있을 때, 곱하면 좋다. 
    function calNeg(arr){
         let total = 0; 
         let n = arr.length; 
         arr.sort((a,b) => a-b)
         if(n === 1) return arr[0]
         if(n %2 === 0){
          for(let i=0; i<=n-2; i+=2){
              total += (arr[i] * arr[i+1])
          }    
        }else{
            for(let i=0; i<=n-3; i+=2){
               total += (arr[i] * arr[i+1])
            }
                total += arr[n-1]
        }
        return total; 
    }
    
    //해당 배열에서 target이하 수가 시작되는 idx 반환 
    function binarySearch(arr, target){
        let start = 0; 
        let end = arr.length -1
        while(start <= end){
            let mid = parseInt((start + end)/2)
            if(arr[mid] > target){
                start = mid + 1
            }else{
                end = mid - 1
            }
        }
        return start; 
    }
}

console.log(solution(arr, N))