Advent of Code 2025 Day 3

오늘도 AOC의 Day 3 문제를 풀어봅시다!
벌써 별이 6개라니 기분 좋네요 ㅎㅎ
24개의 별까지 화이팅해봅시다

Part 1

--- 3일차: 로비 ---
짧은 계단을 내려 놀랍도록 광활한 로비로 들어가면 보안 검색대에 의해 빠르게 통과됩니다. 하지만 메인 엘리베이터에 도착하면 모두 오프라인 상태라는 빨간불이 그 위에 켜져 있는 것을 발견할 수 있습니다.

"죄송합니다." 엘프가 근처 제어판을 만지작거리면서 사과합니다. "어떤 전기 서지가 그들을 튀긴 것 같아요. 곧 온라인에 올리도록 노력할게요."

당신은 더 깊이 들어가야 한다고 설명합니다. "그래, 적어도 에스컬레이터를 타고 인쇄소로 내려갈 수는 있겠지만, 엘리베이터가 작동하지 않으면 그보다 훨씬 더 멀리 갈 수는 없을 거예요. 즉, 에스컬레이터가 오프라인 상태가 아니었다면 그럴 수도 있었죠."

"하지만 걱정하지 마세요! 튀긴 게 아니라 전원만 필요해요. 제가 엘리베이터 작업을 계속하는 동안 작동시켜 주실 수 있나요?"

근처에 에스컬레이터에 비상 전원을 공급할 수 있는 배터리가 있습니다. 배터리에는 각각 1에서 9까지의 충격 등급이 표시되어 있습니다. 충격 등급(퍼즐 입력)을 메모합니다. 예를 들어:

987654321111111
811111111111119
234234234234278
818181911112111
배터리는 뱅크로 배열되어 있으며, 입력된 각 숫자 줄은 하나의 배터리 뱅크에 해당합니다. 각 뱅크 내에서 정확히 두 개의 배터리를 켜야 하는데, 뱅크에서 발생하는 충격은 켜놓은 배터리의 숫자로 형성된 숫자와 같습니다. 예를 들어, 12345와 같은 뱅크가 있고 배터리 2와 4를 켜면 뱅크에서 24개의 충격이 발생합니다. (배터리를 재배열할 수 없습니다.)

각 은행이 생산할 수 있는 가장 큰 충격을 찾아야 합니다. 위의 예시는 다음과 같습니다:

9876543211111에서는 처음 두 개의 배터리를 켜서 가능한 가장 큰 충격인 98을 만들 수 있습니다.
8111111111119에서는 8번과 9번으로 표시된 배터리를 켜서 89번의 충격을 발생시켜 가장 큰 충격을 만들 수 있습니다.
234234234234278에서는 마지막 두 개의 배터리(7과 8로 표시됨)를 켜서 78을 만들 수 있습니다.
818181911112111에서 생산할 수 있는 가장 큰 충격은 92입니다.
총 출력 충격은 각 은행의 최대 충격의 합이므로 이 예제에서 총 출력 충격은 98 + 89 + 78 + 92 = 357입니다.

눈앞에 배터리가 많이 있습니다. 각 뱅크에서 가능한 최대 충격량을 구합니다. 총 출력 충격량은 얼마인가요?

정답

function main(input) {
  const bankList = input.split("\n").map((line) => line.trim());
  let answer = 0;

  // brute force O(N^2)
  bankList.forEach((banks, index) => {
    let max = 0;
    const len = banks.length;

    for (let i = 0; i < len; i++) {
      const start = banks[i];
      for (let j = i + 1; j < len; j++) {
        const end = banks[j];
        const sub = Number(`${start}${end}`);

        max = Math.max(max, sub);
      }
    }
    answer += max;
  });

  console.log(answer);
}

const input = "";

main(input);

해설

단순히 2중 반복문으로 순회해 최대값을 구하는 문제. 최적화를 한다면 O(N)으로도 가능할 것 같다.

Part 2

--- 파트 2 ---
에스컬레이터가 움직이지 않습니다. 엘프는 시스템의 정적 마찰을 극복하려면 더 많은 충격이 필요하다고 설명하며 큰 빨간색 "졸타주 제한 안전 무시" 버튼을 누릅니다. 기다리는 동안 "예, 확실합니다"를 확인하고 로비를 조금 꾸미는 데 필요한 횟수를 셀 수 없습니다.

이제 각 은행마다 정확히 열두 개의 배터리를 켜서 가장 큰 충격을 주어야 합니다.

은행의 충격 출력은 여전히 사용자가 켜놓은 배터리의 숫자로 구성된 숫자입니다. 유일한 차이점은 이제 각 은행의 충격 출력에 두 자리가 아닌 12자리가 있다는 것입니다.

이전의 예를 다시 한 번 생각해 보세요:

987654321111111
811111111111119
234234234234278
818181911112111
이제 충격이 훨씬 더 커졌습니다:

9876543211111에서 가장 큰 충격은 끝에 있는 일부 1을 제외한 모든 것을 켜서 9876543211을 생성함으로써 찾을 수 있습니다.
숫자 시퀀스 에서 가장 큰 충격은 일부 1을 제외한 모든 것을 켜서 811111119를 생성함으로써 찾을 수 있습니다.
234234234278에서 가장 큰 충격은 시작 근처에 있는 2개의 배터리, 3개의 배터리, 그리고 또 다른 2개의 배터리를 제외한 모든 것을 켜서 434234278을 생성함으로써 찾을 수 있습니다.
818181911112111에서는 전면 근처의 일부 1을 제외한 모든 것을 켜서 888911112111이 생산됩니다.
총 출력 충격량은 이제 훨씬 더 커졌습니다: + 8111111119 + 434234234278 + 888911112111 = 312191078619.

새로운 총 출력 충격량은 얼마인가요?

정답

function main(input) {
  const bankList = input.split("\n").map((line) => line.trim());
  let answer = 0;

  // brute force
  bankList.forEach((banks, index) => {
    let _bank = banks;
    let delCnt = _bank.length - 12; // 12자리에 맞춰야함.
    let prevCnt = 0;

    while (delCnt > 0) {
      for (let i in _bank) {
        const nextI = Number(i) + 1;
        if (_bank[i] < _bank[nextI]) {
          const startBank = _bank.slice(0, i);
          const endBank = _bank.slice(Number(i) + 1);
          _bank = `${startBank}${endBank}`;
          delCnt -= 1;
          break;
        }
      }

      // 만약 for문 다 돌았는데도 delCnt가 줄어들지 않았다면? 뒤에서부터 제거
      if (prevCnt === delCnt) {
        _bank = _bank.slice(0, -1);
        delCnt -= 1;
      }
      prevCnt = delCnt;
    }
    answer += Number(_bank);
  });

  console.log(answer);
}

const input2 = `987654321111111
811111111111119
234234234234278
818181911112111`;

main(input);

해설

Part 1의 방식으로하면 12중 반복문( O(N^12) )으로 해결할 수 있겠지만 그건 프로그래머가 아니다. 그리고 너무 오래걸림(N^8마다 1초로 계산할 경우)

이 문제도 간단하다 Banks에서 앞자리를 가장 높게 만들어야한다. 자주 풀던 highest peak 문제와 비슷.
앞에서부터 순회하며 i와 i + 1의 수 중 i가 더 작을 경우 i의 숫자는 제거해 가능한 맨 앞자리를 가장 높게 만든다.
그리고 약간의 예외처리가 필요함.