Advent of Code 2025 Day 5
드디어 별이 2자릿수에 도달했습니다.
새로고침하면 1일차 위의 눈의 위치가 바뀐다는 것을 알고계셨나요... 전 오늘 눈치챘어요.
계속 화이팅!
Part 1
--- 5일차: 카페테리아 ---
지게차가 벽을 뚫고 지나가자 엘프 가족은 결국 반대편에 카페테리아가 있다는 사실을 발견하고 기뻐합니다.
부엌에서 소란이 들려오는 소리가 들립니다. "이 정도면 식당에 화환을 놓을 시간이 전혀 남지 않을 거예요!" 단호하게 조사하세요.
"크리스마스 직전에 새로운 재고 관리 시스템으로 전환하지 않았다면!" 또 다른 엘프가 외칩니다. 무슨 일인지 물어보세요.
주방의 엘프들은 상황을 설명합니다: 복잡한 새로운 재고 관리 시스템 때문에 어떤 재료가 신선하고 어떤 재료가 상했는지 파악할 수 없습니다. 어떻게 작동하는지 물어보면 데이터베이스 사본(퍼즐 입력)을 제공합니다.
데이터베이스는 재료 ID에 따라 작동합니다. 이 데이터베이스는 신선한 재료 ID 범위 목록, 빈 줄, 사용 가능한 재료 ID 목록으로 구성됩니다. 예를 들어:
3-5
10-14
16-20
12-18
1
5
8
11
17
32
신선한 ID 범위는 포함됩니다: 3-5 범위는 재료 ID 3, 4, 5가 모두 신선하다는 것을 의미합니다. 또한 범위가 겹칠 수도 있으며, 재료 ID가 어떤 범위에 속하더라도 신선합니다.
엘프들은 사용 가능한 재료 ID 중 어떤 것이 신선한지 확인하려고 합니다. 이 예제에서는 다음과 같이 수행됩니다:
- 재료 ID 1은 어떤 범위에도 속하지 않기 때문에 손상되었습니다.
- 재료 ID 5는 3-5 범위에 속하기 때문에 신선합니다.
- 재료 ID 8이 손상되었습니다.
- 재료 ID 11은 10-14 범위에 속하기 때문에 신선합니다.
- 재료 ID 17은 16-20 범위와 12-18 범위에 속하기 때문에 신선합니다.
- 재료 ID 32가 손상되었습니다.
따라서 이 예제에서는 사용 가능한 재료 ID 중 3개가 신선합니다.
새 재고 관리 시스템에서 데이터베이스 파일을 처리합니다. 사용 가능한 재료 ID 중 몇 개가 신선한가요?
정답
/**
*
* @param {string} input
*/
function main(input) {
const lines = input.trim().split("\n") ?? [];
const filterIndex = lines.findIndex((line) => line.trim() === "");
const ranges = lines.slice(0, filterIndex).map((l) => l.split("-").map(Number));
const ingredientIds = lines.slice(filterIndex + 1).map(Number);
let answer = 0;
for (const id of ingredientIds) {
for (const [min, max] of ranges) {
if (id >= min && id <= max) {
answer += 1;
break;
}
}
}
return answer;
}
const input = `3-5
10-14
16-20
12-18
1
5
8
11
17
32`;
console.time("main");
const answer = main(input);
console.log("answer:", answer);
console.timeEnd("main");
해설
Part1은 항상 간단합니다. 그냥 brute force로 돌리면돼요!
순회하면서 재료 id가 범위에 포함되는지 확인합니다
Part 2
--- 파트 2 ---
엘프들은 상한 재고를 부엌 뒤편 쓰레기통으로 가져오기 시작합니다.
새로운 재고가 들어오면 방해받지 않도록 엘프들은 신선한 재료 ID 범위가 신선하다고 간주되는 모든 ID를 알고 싶어 합니다. 재료 ID가 어떤 범위에 있든 여전히 신선하다고 간주됩니다.
이제 데이터베이스의 두 번째 섹션(사용 가능한 재료 ID)은 관련이 없습니다. 위 예시의 신선한 재료 ID 범위는 다음과 같습니다:
3-5
10-14
16-20
12-18
이 범위가 신선하다고 간주하는 재료 ID는 3, 4, 5, 10, 11, 12, 13, 14, 15, 15, 16, 17, 18, 19, 20입니다. 따라서 이 예에서 신선 재료 ID 범위는 총 14개의 재료 ID를 신선하다고 간주합니다.
데이터베이스 파일을 다시 처리합니다. 신선한 재료 ID 범위에 따라 신선한 것으로 간주되는 재료 ID는 몇 개입니까?
정답
/**
*
* @param {string} input
*/
function main(input) {
const lines = input.trim().split("\n") ?? [];
const filterIndex = lines.findIndex((line) => line.trim() === "");
const ranges = lines.slice(0, filterIndex).map((l) => l.split("-").map(Number));
ranges.sort((a, b) => a[0] - b[0]);
const mergedRanges = [];
for (const [start, end] of ranges) {
if (mergedRanges.length === 0) {
mergedRanges.push([start, end]);
continue;
}
// 마지막으로 병합된 범위와 비교
const lastRange = mergedRanges[mergedRanges.length - 1];
const [lastStart, lastEnd] = lastRange;
if (start <= lastEnd) {
lastRange[1] = Math.max(lastEnd, end);
} else {
mergedRanges.push([start, end]);
}
}
// 병합된 범위들의 총 ID 개수 계산
let answer = 0;
for (const [start, end] of mergedRanges) {
answer += end - start + 1;
}
return answer;
}
const input = `3-5
10-14
16-20
12-18
1
5
8
11
17
32`;
console.time("main");
const answer = main(input);
console.log("answer:", answer);
console.timeEnd("main");
해설
이 문제는 숫자 범위 간 겹침을 처리해 카운팅할 수 있냐에 대한 문제에요.
단순히 모든 ID를 하나씩 체크할 경우 범위가 크면 제한시간을 넘길 수 있습니다. (N^8을 1초 내에 푸는 게 목적!)그러니까 겹치는 범위들을 병합하여 최종적으로 몇 개의 고유한 ID가 신선한지 계산해야합니다.
- 범위들을 시작점 기준으로 정렬합니다.
- 정렬된 범위들을 순회하며 겹치는 범위를 병합합니다.
- 두 범위가 겹치려면:
현재 범위의 시작점 <= 이전 범위의 끝점- 병합: 끝점을 더 큰 값으로 업데이트
- 병합된 범위들의 총 ID 개수를 계산합니다:
(끝점 - 시작점 + 1)의 합
.
.
예시
- 입력:
3-5, 10-14, 16-20, 12-18- 정렬:
3-5, 10-14, 12-18, 16-20- 병합 과정:
3-5→ 추가10-14→ 추가 (3-5와 겹치지 않음)12-18→10-14와 겹침 (12 <= 14) →10-18로 병합16-20→10-18과 겹침 (16 <= 18) →10-20으로 병합- 최종:
3-5, 10-20- 답:
(5-3+1) + (20-10+1) = 3 + 11 = 14
