[백준 node.js] 1744번_수 묶기

백준 그리디 알고리즘 1138번_한 줄로 서기

난이도 : 실버IV

 

문제 설명

입출력

 

문제 풀이 : 맨 처음에 문제를 읽었을때 이 문제가 골드나 된다고 의심을 품었다. 겉으로 보기에는 너무나 쉬웠다.

하지만 여러가지 고려해야할 사항들이 있다는 것을 나중에 알았다.

 

고려해야할 사항 : 음수들의 곱셈은 양수가 된다!, 1은 덧셈이 더 큰 결과값이 된다!, 0는 양수와 계산할때는 덧셈, 음수와 계산할때는 곱셈!을 해줘야 최대값이 나온다.

 

실패한 첫번째 풀이 방법 : 주어진 입력을 큰 수대로 내림차순 정렬후 반복문을 통해 첫번째 수는 tmp변수에 저장하고 두번째 변수가 나오면 tmp와 곱셈, 덧셈을 각각 한 후 큰 값을 result로 넣어주었다. (*리스트의 길이가 홀수인 경우도 처리해주었다.) 이렇게 해서 테스트 케이스를 통과하여 제출했더니 틀렸다고 나왔다. 여러 테스트 케이스를 만들어 대입 결과 "0" 이 껴있을때 문제가 생겼다. 예를들어 [7, 0, -1]이 있을때 위의 로직대로 행하면 7 + 0 + -1 이 되어서 결과값이 6이된다. 하지만 원래대로라면 7 + (0 * -1)이 되어서 7이 나와야한다.

 

이후 여러가지 시도를 했지만 이미 처음 로직부터 잘못되어 다른 블로그를 참고하였다.

m.blog.naver.com/PostView.nhn?blogId=pjok1122&logNo=221652191176&proxyReferer=https:%2F%2Fwww.google.com%2F

백준 수 묶기 1744번

즉 3가지로 나누어서 로직을 처리해야한다.

첫번째 : 0을 포함한 음수는 작은 수 부터 처리

두번째 : 1보다 큰 수는 큰 수부터 처리.

세번째 : 숫자가 1인 경우에는 덧셈 진행.

 

이를 통해 해결할 수 있었다.

// 골드4 수 묶기

function solution(n, list) {
  //0과 음수 리스트
  let negative = [];
  //양수 리스트
  let positive = [];
  let result = 0;

  for (i of list) {
    if (i <= 0) {
      negative.push(i);
    } else if (i > 1) {
      positive.push(i);
    } else if (i === 1) {
      // 숫자가 1인경우는 덧셈이 더 큰 수를 가지므로 미리 계산해준다.
      result += i;
    }
  }

  //큰 값들 부터 계산해야하기 때문에 음수와 양수 정렬

  //양수는 내림차순
  positive.sort(function (a, b) {
    return b - a;
  });

  //음수는 오름차순
  negative.sort(function (a, b) {
    return a - b;
  });

  //양수 리스트 길이에 맞게 반복문
  for (let i = 0; i < positive.length; i += 2) {
    if (i + 1 < positive.length) {
      result += positive[i] * positive[i + 1];
    } else {
      result += positive[i];
    }
  }

  //음수 리스트 길이에 맞게 반복문
  for (let j = 0; j < negative.length; j += 2) {
    if (j + 1 < negative.length) {
      result += negative[j] * negative[j + 1];
    } else {
      result += negative[j];
    }
  }
  console.log(result);

}

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  //n개
  let n = input[0];
  //수열 list
  let list = input.slice(1);
  list = list.map((el) => parseInt(el));
  solution(n, list);
  process.exit();
});

 

* JS 정렬 방법은 위의 방법을 통해서 진행해야한다.(sort만 사용할지 ASCII 크기 순으로 정렬하기 때문에 제대로 정렬x)

 

 

*실패한 로직 (입출력까진 동일)

    //큰 수 부터 계산하기 위해 내림차순
    list.sort(function (a, b) {
      return b - a;
    });

    // 곱셈 결과값
    let result = 0;
    // 덧셈 결과값 
    let result1 = 0;
    // 첫번째, 두번째 값을 카운트해주는 변수
    let cnt = 0;
    // 첫번째 값 임시저장 변수
    let tmp = 0;
    //최종 결과값
    let r = 0;
    for (let i = 0; i < n; i++) {
      cnt += 1;

      if (cnt === 2) {
        cnt = 0;
        result = tmp * list[i];
        result1 = tmp + list[i];
        r -= tmp;
        r += Math.max(result, result1);
      } else {
        tmp = list[i];
        r += tmp;
      }
    }

   console.log(r);