99클럽 코테 스터디 24일차 TIL - [프로그래머스] 대충 만든 자판 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 대충 만든 자판 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/160586

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap, 입력하려는 문자열들이 담긴 문자열 배열 targets
출력 : 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 출력. 단, 목표 문자열을 작성할 수 없을 때는 -1 출력

가능한 시간복잡도

O(n)

알고리즘 선택

그래프

📌 코드 설계하기

1. keyPressMap: 각 문자가 어떤 키에 몇 번 눌려야 하는지를 기록합니다. 예를 들어, A는 1번, B는 2번 등으로 기록됩니다.

2. keymap 배열 처리: 모든 키맵을 순회하면서 각 문자가 몇 번째 키에 위치하는지 계산합니다. 이때, 같은 문자가 여러 키에 있을 경우 최소값을 저장합니다.

3. targets 처리: 주어진 타겟 문자열을 순회하면서 각 문자에 대해 최소 키 횟수를 합산합니다. 만약 특정 문자를 입력할 수 없으면 -1을 반환합니다.

4. 출력: 최종적으로 각 타겟에 대해 계산된 키 횟수 배열을 반환합니다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

public class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        // 각 문자에 대해 최소 키 횟수를 저장하는 맵을 생성
        Map<Character, Integer> keyPressMap = new HashMap<>();

        // 키맵 배열에서 각 문자에 대한 최소 키 횟수를 계산
        for (String key : keymap) {
            for (int i = 0; i < key.length(); i++) {
                char ch = key.charAt(i);
                int keyPressCount = i + 1;  // 1-based index

                // 해당 문자가 이미 맵에 있으면, 현재 계산한 키 횟수와 비교하여 더 작은 값으로 업데이트
                keyPressMap.put(ch, Math.min(keyPressMap.getOrDefault(ch, Integer.MAX_VALUE), keyPressCount));
            }
        }

        // 각 타겟 문자열에 대해 필요한 키 횟수를 계산
        int[] answer = new int[targets.length];
        for (int i = 0; i < targets.length; i++) {
            String target = targets[i];
            int keyPressSum = 0;

            for (char ch : target.toCharArray()) {
                if (!keyPressMap.containsKey(ch)) {
                    // 해당 문자를 입력할 수 없다면 -1을 저장
                    keyPressSum = -1;
                    break;
                }
                keyPressSum += keyPressMap.get(ch);
            }

            answer[i] = keyPressSum;
        }

        return answer;
    }
}