https://school.programmers.co.kr/learn/courses/30/lessons/160586
이번에 풀어본 문제는 이 문제다.

문제

문제를 보니 예전 피쳐폰 사용할 때 이렇게 되어있었던 것 같은데... 라는 생각이 들었다.

입출력 예

사실 처음에는 이해가 잘 안갔다.
keymap[1]에서 targets[1]을 출력하는 줄 알았는데 어느 맵에서든 만들면 되는 문제였다.

이 정도만 알고 문제 풀이를 시작해도 될 것 같다.

코드

Map 만들기

문제도 Map을 썼으니 나도 Map을 하나 만들어보겠다.

HashMap<Charater, Integer> newKeymap = new HashMap<>();

위와 같은 맵을 하나 만들었다.

해당 맵은 존재하는 keymap의 철자별로 순서를 나타내는 맵이기 때문에 char형태와 int 형태가 key-value 형태로 저장된다.

map 만들기 중 문제

그런데 map을 만들다 보면 겹치는 알파벳이 보인다 A라던가 B등

그렇다면 map을 만들 때 두 번째로 나오는 알파벳의 인덱스에 따라 value가 변경될 테니 이미 map에 존재한다면 최소값으로 value를 저장하는 코드까지 추가해주자.

for (String key : keymap) {
    for (int i = 0; i < key.length(); i++) {
        char c = key.charAt(i);
                
        // 이미 맵에 존재한다면 i를 통해 더 작은 값으로 value를 변경
        if (newKeymap.containsKey(c)) {
            newKeymap.put(c, Math.min(newKeymap.get(c), i + 1));
        } else {
            // 맵에 존재하지 않는다면 새로 map에 생성
            newKeymap.put(c, i + 1);
        }
    }
}

왜 위의 코드와 같이 저장했냐면
우리가 target을 출력하기 위한 최소 버튼수가 Map에 저장된 value의 형태로 저장되기 때문이다.

이제 Targets를 추적할 차례

이제 targets도 역시 똑같은 방법으로 알파벳을 하나씩 분리하여
만들어둔 맵을 사용한다면 값을 가져올 수 있다.

// 목표 문자열 작성 최소 횟수 계산
for (int t = 0; t < targets.length; t++) {
    String target = targets[t];
    int result = 0;

    for (int i = 0; i < target.length(); i++) {
        char c = target.charAt(i);

        if (!newKeymap.containsKey(c)) {
            // 목표 문자열을 만들 수 없는 경우
            result = -1;
            break;
        } else {
            result += newKeymap.get(c);
        }
    }
}

이제 target의 알파벳 하나를 통해 해당 알파벳의 최소값을 Map에서부터 가져올 수 있고,
해당 최소값을 target의 길이만큼 반복하면 target을 만드는데 필요한 최소 버튼 수를 구할 수 있다.

전체코드

import java.util.*;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        // map 이니까 map을 써보자
        HashMap<Character, Integer> newKeymap = new HashMap<>();

        for (String key : keymap) {
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);
                
                // 이미 맵에 존재한다면 i를 통해 더 작은 값으로 value를 변경
                if (newKeymap.containsKey(c)) {
                    newKeymap.put(c, Math.min(newKeymap.get(c), i +1));
                } else {
                    // 맵에 존재하지 않는다면 새로 map에 생성
                    newKeymap.put(c, i+1);
                }
            }
        }
        
        int[] answer = new int[targets.length];

        // 목표 문자열 작성 최소 횟수 계산
        for (int t = 0; t < targets.length; t++) {
            String target = targets[t];
            int result = 0;

            for (int i = 0; i < target.length(); i++) {
                char c = target.charAt(i);

                if (!newKeymap.containsKey(c)) {
                    // 목표 문자열을 만들 수 없는 경우
                    result = -1;
                    break;
                } else {
                    result += newKeymap.get(c);
                }
            }
            answer[t] = result;
        }
        
//        for (Map.Entry<Character, Integer> entry : newKeymap.entrySet()) {
//            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
//        }


        return answer;
    }
}