younganswer
Problem SolvingApr 3, 2026

[프로그래머스] 136797 숫자 타자 대회 (javascript)

#Problem Solving#Coding Test#Algorithm#Programmers#136797#Dynamic Programming#Memoization
[프로그래머스] 136797 숫자 타자 대회 (javascript)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/136797



풀이

접근 방식

최적해를 구하는 문제이다. 역시 처음에는 완전 탐색부터 고려했다. 입력 길이의 최댓값이 100,000100,000 이고, 각 자리마다 어느 손으로 누를지 선택이 갈릴 수 있으므로 단순 완전 탐색은 현실적으로 불가능하다는 것을 바로 알 수 있었다.

이어서 자연스럽게 그리디 알고리즘도 고려했다. 하지만 지역 최적해가 전역 최적해를 보장하지 않음을 몇 가지 반례를 통해 쉽게 확인할 수 있었다.

마지막으로 동적 계획법을 고려했다. 상태의 정의가 명확하고 비교적 가짓 수도 많지 않아 그대로 진행했다. 메모이제이션 방식도 시도해보고, 테이블 기반 DP로도 풀어보다가, 이것저것 해본 끝에 결국에는 BFS에서 현재 queue를 소모한 뒤 다음 queue를 다시 만드는 방식처럼, 현재 상태 Map을 기반으로 다음 상태 Map을 새로 구성하는 형태로 구현했다.


놓친 점

  1. 처음에는 dr === 0 && dc === 0 인 경우를 weight 함수 안에서 처리했었다. 그런데 두 손가락 중 하나가 다음 위치 위에 올라와 있을 때, 다른 손가락이 그 위치로 겹쳐질 수 없음이 문제 조건이라는 점을 간과하고 있어서 이 부분 때문에 정말 오래 디버깅했다.

    이후에 알아차렸을 때도 그래도 최종적으로 같은 결과를 보장하지 않나? 왜 달라지지? 했는데, 멀리 있는 손가락이 해당 손가락의 위치에 와서 겹쳤을 때 그 순간의 비용은 증가할 수 있으나 이후 전역 최적해가 더 감소할 수 있음을 깨닫고 나서 이 부분을 수정했다.

    알고리즘적인 아이디어 자체가 유난히 어려운 문제는 아니었는데, 오히려 구현에서 생각보다 난도가 있어서 조금 당황했던 문제였다.

  2. 문제 조건에 numbers 인자에는 '*' 과 '#' 이 들어오지 않는다고 명시되어 있다. 어쩐지 인자명이 numbers 더라. 괜히 더 어렵게 풀고 있었다.


+) key trick 과 distance trick 은 정답 처리 이후에 개선해보았다.



정답 코드

javascript
const POSITION = [
	[3, 1], // 0
	[0, 0], [0, 1], [0, 2], // 1, 2, 3
	[1, 0], [1, 1], [1, 2], // 4, 5, 6
	[2, 0], [2, 1], [2, 2], // 7, 8, 9
]

const DISTANCE = Array.from({ length: 10 }, (_, from) =>
    Array.from({ length: 10 }, (_, to) => {
        if (from === to) {
            return 1;
        }

        const [fr, fc] = POSITION[from];
        const [tr, tc] = POSITION[to];
        const dr = Math.abs(fr - tr);
        const dc = Math.abs(fc - tc);

        return 3 * Math.min(dr, dc) + 2 * Math.abs(dr - dc);
    })
);

const BASE = 10;
const encode = (left, right) => left * BASE + right;
const decode = (key) => [Math.floor(key / BASE), key % BASE];

const solution = (numbers) =>
    Math.min(...[...numbers].map(Number).reduce(
        (map, number) => {
            const ret = new Map();
			const set = ([key, value]) => ret.set(key, Math.min(ret.get(key) ?? Infinity, value));
            
            for (const [ key, cost ] of map.entries()) {
                const [ left, right ] = decode(key);
				const next = left === number || right === number
					? [[key, cost + 1]]
					: [
						[encode(number, right), cost + DISTANCE[left][number]],
						[encode(left, number), cost + DISTANCE[right][number]]
					];
					
				next.forEach(set);
            }
            
            return ret;
        },
        new Map([[encode(4, 6), 0]])
    ).values());

Share this post

N