[JS][백준]16206_롤케이크

문제 번호

16206번: 롤케이크

 

 

 

알고리즘 분류

• 그리디 알고리즘

 

문제 풀이

 그리디 알고리즘을 사용한다. 정렬기준을 생각하는데 매우 오래걸렸다. 

주어진 롤케이크들을 오름차순으로 정렬하되, 10의 배수이면 더 앞쪽에 위치하도록 한다.

예를들어 15 20 25 30 35 가 있다고 하자. 그렇다면 20 30 15 25 35 순서로 배치가 되어야한다. 10의 배수들을 따로 빼서 앞쪽에 오름차순으로 배치하고 나머지 숫자들을 오름차순으로 이어서 배치하면된다.

 

  cakes.sort((a, b) => {
    if (a % 10 === 0 && b % 10 === 0) {
      if (a < b) return -1;
      else if (a > b) return 1;
      return 0;
    } else if (a % 10 === 0 && b % 10 !== 0) {
      return -1
    } else if (a % 10 !== 0 && b % 10 === 0) {
      return 1;
    } else if (a % 10 !== 0 && b % 10 !== 0) {
      if (a < b) return -1;
      else if (a > b) return 1;
      return 0;
    }
  })

 

이제 정렬된 케이크들을 확인하면서 크기가 10보다 크다면 잘라주면서 진행하면된다. 크기가 딱 10이라면 자를 필요없이 정답값만 증가시켜주면 된다.

  for (let i = 0; i < cakes.length; i++) {
    while (cakes[i] > 10) {
      if (M <= 0)
        break;
      cakes[i] -= 10;
      answer++;
      M--;
    }
    if (cakes[i] === 10) {
      answer++;
    }
    if (M <= 0)
      break;
  }

 

전체코드

/*
 * 오름차순으로 정렬하는데 10의 배수면 더 앞쪽에 오게한다.
 */
const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
let [N, M] = input[0].split(' ').map(Number);
let cakes = input.slice(1)[0].split(' ').map(Number);

function main() {
  let answer = 0;

  cakes.sort((a, b) => {
    if (a % 10 === 0 && b % 10 === 0) {
      if (a < b) return -1;
      else if (a > b) return 1;
      return 0;
    } else if (a % 10 === 0 && b % 10 !== 0) {
      return -1
    } else if (a % 10 !== 0 && b % 10 === 0) {
      return 1;
    } else if (a % 10 !== 0 && b % 10 !== 0) {
      if (a < b) return -1;
      else if (a > b) return 1;
      return 0;
    }
  })


  for (let i = 0; i < cakes.length; i++) {
    while (cakes[i] > 10) {
      if (M <= 0)
        break;
      cakes[i] -= 10;
      answer++;
      M--;
    }
    if (cakes[i] === 10) {
      answer++;
    }
    if (M <= 0)
      break;
  }


  return console.log(answer)
}
main();

특이사항

 정렬 기준을 생각하는데 매우 오래걸렸다. 몫, 나머지 등등 다 생각해봤었는디 ..... 여러가지 기준을 섞어서 사용하는 방법도 종종 생각해보자.