1. 문제

대충 만든 자판



2. 개요

휴대폰 자판은 키보드 자판과는 다르게 한 키에 여러 문자가 할당될 수 있다. 이러한 경우 동일한 키를 빠르게 여러 번 눌러 다른 문자를 입력할 수 있다.

한 핸드폰 자판이 있다. 이 자판은 같은 문자가 자판 전체에 걸쳐 여러 번 할당되었을 수도 있고, 키 하나에 같은 문자가 여러 번 할당되었을 수도 있으며, 아예 할당되지 않을 수도 있다.

핸드폰 자판의 키 배열과, 입력하려는 문자열 배열이 주어졌을 때, 각 목표 문자열에 대해 키를 눌러야 하는 최소 횟수를 구하는 문제.



3. 풀이 및 코드

3-1. 풀이

모든 대문자 알파벳 입력에 대해 눌러야 하는 최소 횟수를 저장할 길이 26짜리의 배열을 만들고 최댓값으로 초기화 해둔다.

주어진 키 배열을 탐색하면서 각 알파벳에 대해 지금까지 저장된 버튼 입력 최소 횟수와 지금의 입력 횟수를 비교하여 최솟값으로 갱신해나간다.

모든 키 배열에 대해 탐색을 마친 뒤, 타겟 문자열들을 하나하나 탐색하면서 각 알파벳에 저장된 최소 횟수를 더하고, 최종적으로 배열에 값을 저장한다.

모든 탐색을 마치고, 정답 배열을 리턴한다.

3-2. C#

using System;

public class Solution {
    public int[] solution(string[] keymap, string[] targets) {
        int[] answer = new int[targets.Length];

        int[] alpha = new int[26];
        Array.Fill(alpha, int.MaxValue);

        foreach (string key in keymap)
        {
            for (int i = 0; i < key.Length; i++)
            {
                alpha[key[i] - 65] = i + 1 < alpha[key[i] - 65] ? i + 1 : alpha[key[i] - 65];
            }
        }

        bool cando = true;
        for (int i = 0; i < answer.Length; i++)
        {
            cando = true;

            for (int j = 0; j < targets[i].Length; j++)
            {
                if (alpha[targets[i][j] - 65] == int.MaxValue)
                {
                    cando = false;
                    break;
                }

                answer[i] += alpha[targets[i][j] - 65];
            }

            if (!cando)
                answer[i] = -1;
        }

        return answer;
    }
}

Comments