[프로그래머스/Java] 대충 만든 자판

문제 설명

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

프로그래머스

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.

같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.

이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.

단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

제한 사항

• 1 ≤ keymap의 길이 ≤ 100
  • 1 ≤ keymap의 원소의 길이 ≤ 100
  • keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.
    • 예를 들어 keymap[0] = "ABACD"인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다.
  • keymap의 원소의 길이는 서로 다를 수 있습니다.
  • keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
• 1 ≤ targets의 길이 ≤ 100
  • 1 ≤ targets의 원소의 길이 ≤ 100
  • targets의 원소는 알파벳 대문자로만 이루어져 있습니다.

입출력 예

keymap	targets	result
["ABACD", "BCEFD"]	["ABCD", "AABB"]	[9, 4]
["AA"]	["B"]	[-1]
["AGZ", "BSSS"]	["ASA", "BGZ"]	[4, 6]

입출력 예 설명

입출력 예 #1

• "ABCD"의 경우,
  1번 키 한 번 → A
  2번 키 한 번 → B
  2번 키 두 번 → C
  1번 키 다섯 번 → D
  따라서 총합인 9를 첫 번째 인덱스에 저장합니다.
• "AABB"의 경우,
  1번 키 한 번 → A
  1번 키 한 번 → A
  2번 키 한 번 → B
  2번 키 한 번 → B
  따라서 총합인 4를 두 번째 인덱스에 저장합니다.
• 결과적으로 [9,4]를 return 합니다.

입출력 예 #2

• "B"의 경우, 'B'가 어디에도 존재하지 않기 때문에 -1을 첫 번째 인덱스에 저장합니다.
• 결과적으로 [-1]을 return 합니다.

입출력 예 #3

• "ASA"의 경우,
  1번 키 한 번 → A
  2번 키 두 번 → S
  1번 키 한 번 → A
  따라서 총합인 4를 첫 번째 인덱스에 저장합니다.
• "BGZ"의 경우,
  2번 키 한 번 → B
  1번 키 두 번 → G
  1번 키 세 번 → Z
  따라서 총합인 6을 두 번째 인덱스에 저장합니다.
• 결과적으로 [4, 6]을 return 합니다.

 

내가 작성한 코드

import java.util.*;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        // 각 알파벳의 최소 입력 횟수 저장 (A ~ Z)
        int[] minCount = new int[26];
        // 처음에는 가장 큰 값 저장
        Arrays.fill(minCount, Integer.MAX_VALUE);
        
        // keymap을 활용해 최소 입력 횟수 확인
        for (String key : keymap) {
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);
                // 각 알파벳의 인덱스 확인
                int idx = c - 'A';
                // 같은 문자가 여러 keymap에 있을 수 있으니 최소값으로 유지
                minCount[idx] = Math.max(1, Math.min(minCount[idx], i + 1));
            }
        }
        
        // 편의를 위해 targets의 길이 저장
        int len = targets.length;
        int[] answer = new int[len];
        
        // 각 target 문자열에 필요한 입력 횟수 계산
        for (int i = 0; i < len; i++) {
            String s = targets[i];
            int count = 0;
            // 입력이 불가능한 경우를 위한 변수 생성
            boolean possible = true;
            
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                int idx = c - 'A';
                
                // 조건에 해당하면 어떤 키에서도 만들 수 없음
                if (idx < 0 || idx >= 26 || minCount[idx] == Integer.MAX_VALUE) {
                    possible = false;
                    break;
                }
                
                // 문자에 필요한 입력 횟수 합산
                count += minCount[idx];
            }
            
            // 생성이 불가능한 경우 -1 저장
            answer[i] = possible ? count : -1;
        }
        
        // 정답 반환
        return answer;
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때, 각 타겟 문자열을 만들기 위해 필요한 최소 키 입력 횟수를 구하는 문제라고 이해했으며, 핵심은 매번 keymap을 전부 탐색하지 않고 문자별 최소 입력 횟수를 미리 계산해 두는 전처리가 필요하다고 판단했다.

조건을 분석해 보면, 같은 문자가 여러 키맵의 서로 다른 위치에 등장할 수 있으므로 해당 문자를 누르는 데 걸리는 횟수는 “등장 위치 + 1” 값들 중 최솟값이 되어야 한다는 점이 중요하다. 또한 어떤 문자든 keymap 어디에도 없다면 그 문자가 포함된 타겟은 애초에 만들 수 없으므로 결과를 -1로 처리해야 한다.

자료구조는 알파벳 대문자만 다루므로 HashMap 대신 길이 26짜리 int[]를 선택하는 것이 합리적이라 판단했다. 배열 인덱싱이 해시보다 빠르고, 공간도 고정적이며 단순하다. 초기값은 Integer.MAX_VALUE로 채워 두어 아직 관측되지 않은 문자를 자연스럽게 구분하고, 관측될 때마다 min 갱신으로 최소 입력 횟수를 유지하도록 했다.

로직 흐름은 다음과 같다. 먼저 전처리 단계에서 모든 keymap 문자열을 순회하며 각 문자 c가 i번째 위치에 있으면 minCount[c-'A'] = min(minCount[c-'A'], i+1)로 갱신했다. 그런 다음 각 targets[i]에 대해 문자를 왼쪽부터 보며 minCount에서 해당 문자의 최소 입력 횟수를 합산한다. 이때 값이 여전히 Integer.MAX_VALUE라면 해당 문자는 어떤 키에서도 만들 수 없다는 뜻이므로 즉시 불가능 플래그를 세우고 결과를 -1로 기록했다. 전부 유효하다면 누적 합을 그대로 답에 넣었다.