안녕하세요! 이번 블로그 글에서는 자바스크립트 코딩테스트를 대비하기 위한 알고리즘 문제를 다뤄보겠습니다. 주제는 ‘블루레이 만들기’입니다. 이 문제는 주어진 영화를 블루레이로 만들 때 필요한 최소의 블루레이 장수를 구하는 것입니다. 이를 해결하기 위해서는 이분 탐색과 그리디 알고리즘을 활용해야 할 것입니다.
문제 설명
당신은 여러 영화를 블루레이로 만들고 싶습니다. 각 영화의 상영 시간이 주어지며, 블루레이에는 최대 K만큼의 시간을 담을 수 있습니다. 당신의 목표는 블루레이의 수를 최소화하여 모든 영화를 블루레이에 담는 것입니다. 단, 각 블루레이에는 상영 시간이 K를 넘지 않도록 영화들을 배분해야 합니다.
입력
- 첫 줄에는 N과 K가 주어집니다. (1 ≤ N ≤ 1000, 1 ≤ K ≤ 10^6)
- 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 각 영화의 상영 시간이 주어집니다. (1 ≤ 영화의 상영 시간 ≤ 10^6)
출력
블루레이의 최소 개수를 출력합니다.
예시
입력: 4 5 2 3 1 4 출력: 2
문제 풀이 과정
이 문제를 접근하기 위해서는 다음의 단계로 진행할 수 있습니다.
1단계: 문제 이해
주어진 영화를 최대 K의 상영 시간을 갖는 블루레이에 어떻게 배분할 것인가를 고민합니다. 각 영화의 상영 시간이 주어졌고, 이 시간을 합쳐 K를 넘지 않는 범위 내에서 블루레이에 담아야 하므로, 가능한 경우의 수를 고려해야 합니다.
2단계: 아이디어 도출
모든 영화를 단순하게 하나의 블루레이에 담을 수는 없으므로, 영화 리스트를 반복적으로 탐색하면서 각 블루레이에 담아도 되는지를 확인합니다. 이를 위해서 이분 탐색을 활용하여 블루레이의 최소 개수를 찾는 방법을 사용할 것입니다.
3단계: 예외 처리
각 영화를 담는 시간이 최대 K를 초과하면, 해당 영화를 새로운 블루레이에 담아야 합니다. 이 조건을 주의하여 최대한 많은 영화를 블루레이에 담는 것이 중요합니다.
4단계: 알고리즘 구현
이제 위의 아이디어를 기반으로 자바스크립트 함수를 구현하겠습니다.
function minBluRays(N, K, movies) {
let bluRays = 0;
let currentTime = 0;
for (let i = 0; i < N; i++) {
if (currentTime + movies[i] > K) {
bluRays++;
currentTime = movies[i];
} else {
currentTime += movies[i];
}
}
if (currentTime > 0) {
bluRays++;
}
return bluRays;
}
// 예제 실행
const N = 4;
const K = 5;
const movies = [2, 3, 1, 4];
console.log(minBluRays(N, K, movies)); // 출력: 2
결론
이번 글에서는 ‘블루레이 만들기’ 문제를 통해 자바스크립트 코딩테스트에서 자주 등장하는 알고리즘 문제를 풀이하는 과정을 보여주었습니다. 문제의 본질을 이해하고, 필요한 알고리즘을 찾는 것이 매우 중요합니다. 주어진 시간을 잘 활용하여 효율적인 코드를 작성하는 것이 좋습니다.
이 문제를 통해 자바스크립트의 기본적인 사용법과 알고리즘적인 사고 방식을 개발할 수 있기를 바랍니다. 감사합니다!