백준 10819번: 차이를 최대로 - javascript

백준 10819번: 차이를 최대로

문제 설명

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

A[0] - A[1]

+

A[1] - A[2]

+ … +

A[N-2] - A[N-1]

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

접근

처음에는 규칙을 찾으려고 해봤다.
대충 제일 작은 값 , 제일 큰 값, 그다음으로 제일 작은 값… 이런순서로 지그재그로 놓아보려고 했는데 전혀 아니였다.
이번계기로 약간? 문제를 보는 시각을 다르게 했는데, 먼저 주어진 입력범위가 하나의 힌트다.
그냥 내 개인적인 느낌이다.

먼저 N은 3보다 크고 8보다 작다고 한다. 이런 작은 범위의 수열 문제 어디서 봤는데…
맞다. 지난 몇 일 간 주구장창 풀었던 백준 N과M의 범위다.
[N과M]에서도 N의 범위는 1보다 크고 9보다 작은~ 으로 나온다.
즉 수열의 배치를 구하는게 아니라 모든 배치를 구해놓고 풀으면 된다는 뜻.

그래서 수열의 모든 경우를 만들어주는 함수 re()를 백준 N과M 풀이에서 가져와서 조금 손봤다.
그리고 모든 수열을 구하게 되면 우리는 수열 간의 차이의 절대값의 합을 비교해서 max값을 찾아야한다.
간단하다.
re() 함수에서 만들어낸 모든 수열의 경우가 들어있는 배열을 반복문으로 돌린다.
각 인덱스에는 스트링으로 들어간 수열이 있을 것이고, 이 문자열을 split을 사용해서 또 하나의 배열로 만들어준다.

이제 이 배열을 반복문을 이용해서 배열의 길이-1 만큼 돌려주면서 현재i행과 i+1행간의 차이의 절대값을 누산해간다.
최종적으로 max변수를 두어 매 수열마다 이를 비교하게 한다.
그러면 최종적으로 max값을 가지고 있을 것이므로 이를 반환한다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let list = [];
let result = [];
let numbers = [];
let check = new Array(9).fill(false);
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer =0;  
  
  numbers = input[1].split(' ').sort((a,b) => a-b);
  let n = input[0];
  re(0,n,0);  
  //console.log(result.join('\n'));  
  console.log(max_abs());
  process.exit();
});

let max_abs = function(){
  let max = 0;
  result.reduce((acc,cur)=>{
    let tmp = cur.split(' ');
    let sum = 0;
    for(let i=0;i<tmp.length-1;i++){
      sum += Math.abs(tmp[i]*1-tmp[i+1]*1);
    }
    max = Math.max(max, sum);
  },'')
  return max;
}
 
let re = function(cnt,n,start){
  if(cnt==n){    
    result.push(list.join(' '))
    return ;
  }
  for(let i=start;i<n;i++){
    if(!check[i]){      
      check[i] = true;
      list[cnt] = numbers[i];
      re(cnt+1,n,0);      
      check[i] = false;
    }
  }
}