대충만든 자판 알고리즘 알고리즘 소개

이번 글에서는 프로그래머스의 대충 만든 자판 알고리즘의 문제풀이를 해보도록 한다.

주어진 키맵과 타겟 문자열을 바탕으로, 각 문자를 입력하는 데 필요한 최소한의 타이핑 횟수를 계산하는 알고리즘 문제이다.

알고리즘은 각 문자를 입력하기 위한 가장 효율적인 경로를 찾고, 만약 타겟 문자열의 문자를 입력할 수 없는 경우에는 -1을 반환한다.

문제는 두 가지 입력을 받는다.

keymap: 여러 개의 키맵 문자열 배열로, 각 키맵은 사용자가 타이핑할 수 있는 키의 배열이다. 각 키맵은 자판의 레이아웃과 유사하게 생각할 수 있다.

targets: 사용자가 입력하고자 하는 문자열 배열이다. 이 배열에 있는 각 문자열이 입력될 때, 각 문자를 타이핑하는 데 걸리는 최소한의 횟수를 계산하는 것이 목적이다.

아래는 직접 작성한 문제의 풀이이다. 보시다시피, 알고리즘은 크게 두 단계로 나뉜다.

키맵 분석: 각 키맵을 분석하여, 각 문자를 타이핑하기 위한 최소한의 횟수를 기록한다.

타겟 분석: 타겟 문자열을 순회하며, 각 문자를 입력하기 위한 최소 타이핑 횟수를 계산하거나 입력이 불가능한 경우 -1을 반환한다.

    if (keymap.length < 1 || keymap.length > 100) return;

    if (targets.length < 1 || targets.length > 100) return;

    const keymapIndexWithOptimizedPath = new Map();

    if (keymapItem.length < 1 || keymapItem.length > 100) return;

    for (let i = 0; i < keymapItem.length; i++) {

        const eachLetter = keymapItem.charAt(i);

        const prevLetterTypingCount = keymapIndexWithOptimizedPath.get(eachLetter);

        const currentLetterTypingcount = i + 1;

        if (!prevLetterTypingCount || currentLetterTypingcount < prevLetterTypingCount) {

        keymapIndexWithOptimizedPath.set(eachLetter, currentLetterTypingcount);

targets.forEach((targetsItem, targetsItemIndex) => {

        if (targetsItem.length < 1 || targetsItem.length > 100) return;

        for (let i = 0; i < targetsItem.length; i++) {

            const eachLetter = targetsItem.charAt(i);

            // find letter from the key map index with optimized path

            const keymapIndex = keymapIndexWithOptimizedPath.get(eachLetter);

            // if key map index exist, add value to an answer

            initialValue = keymapIndex + initialValue;

            answer[targetsItemIndex] = initialValue;

                answer[targetsItemIndex] = -1;

먼저 키맵 배열을 순회하면서 각 키맵의 문자를 입력하기 위한 타이핑 횟수를 기록한다. 예를 들어, 첫 번째 키맵 "ABACD"에서는 'A'는 1번, 'B'는 2번, 'C'는 3번, 'D'는 5번 타이핑해야한다.

            keymapIndexWithOptimizedPath.set(eachLetter, currentLetterTypingcount);

위 코드에서는 키맵을 순회하면서 각 문자의 입력 횟수를 기록한다. 만약 이미 기록된 횟수가 있다면, 더 적은 횟수로 타이핑할 수 있는 경우에만 값을 업데이트한다.

대충만든 자판

Body Parser란?