[백준 1715] 카드 정렬하기
March 12, 2023
문제
https://www.acmicpc.net/problem/1715
아이디어
숫자 카드 묶음을 합칠 때 비교 횟수를 최소로 하기 위해서는 가장 작은 크기의 숫자 카드끼리 먼저 합쳐야 한다. (그리디)
그렇기에 기본 입력 값의 숫자 카드 묶음을 오름차순으로 정렬하여 큐로 만들어놓고 가장 작은 두 개의 카드 묶음을 꺼내어 합친다.
합친 카드 묶음은 다시 큐에 넣어서 다른 카드 묶음과 합치는 과정을 반복한다.
풀이 중 발생한 문제
이 문제를 제출하면서 몇 번의 시행 착오를 겪었는데
- 처음에는 큐의 끝 부분에 새로 합친 카드 묶음을 먼저 추가하고 그 이후에
Array.prototype.sort함수로 정렬을 했었는데 시간 초과가 났다.
그래서Array.prototype.findIndex로 새로 들어가야 할 인덱스 위치를 찾은 뒤에Array.prototype.splice로 정확한 위치에 요소를 추가해줬다. - 초기 입력 값
n이 1이면 그 카드 묶음의 크기를 기본적으로 출력해야 하는줄 알았는데, 그게 아니라 카드 묶음을 합칠 때의 비교 횟수만 출력해야 하는 것이었다.
소스코드
// 입력 처리
const INPUT_NAME = 'i4.txt';
const filePath = process.platform === 'linux' ? '/dev/stdin' : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require('fs').readFileSync(filePath).toString().trim().split('\n').map(item => item.trim());
const n = Number(input[0]);
const cards = input.map((v, i) => (i > 0) && (i <= n) ? Number(v) : 0);
cards.shift();
cards.sort((a, b) => a - b);
// 문제
function solution() {
let result = 0;
// 문제 이해를 잘못 했던 부분이다.
// if (cards.length === 1) result += cards[0];
// 카드 묶음이 아직 2개 이상 남았다면 그 카드 묶음을 합쳐줘야한다.
while (cards.length >= 2) {
const a = cards.shift();
const b = cards.shift();
const sum = a + b; // 두 카드 묶음을 합쳐준다.
result += sum;
// 방금 합친 카드 묶음을 큐에 넣어준다.
const index = cards.findIndex(e => e > sum); // 정렬 되어있는 큐의 어느 위치에 삽입해야 하는지를 찾는다.
cards.splice(index !== -1 ? index : cards.length, 0, sum);
}
console.log(result);
}
// 실행
solution();