16일차 - 알고리즘 코드카타

- 회고

66. 대충 만든 자판 https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int[] result = new int[targets.length];
        for(int i = 0; i < targets.length; i++){
           int answer = 0;
           for(int j = 0; j < targets[i].length(); j++){
               char c = targets[i].charAt(j);
               int push = Integer.MAX_VALUE;
               for(int q = 0; q < keymap.length; q++){
                   if(keymap[q].indexOf(c) != -1 && push > keymap[q].indexOf(c)){
                       push = keymap[q].indexOf(c) + 1;
                   }
               }
               if(push == Integer.MAX_VALUE){
                   answer = -1;
                   break;
               }else{
                   answer += push;
               }
           }
           result[i] = answer;
       }
        return result;
    }
}

- 풀이 과정 

1. targets을 도는 첫번째 for문
2. targets의 각 단어에 접근하는 두번째 for문
3. keymap에 접근하는 세번째 for문
4. String.indexOf()로 포함여부 확인(포함되지 않으면 -1을 반환함)
5. 최소 입력값을 구해야하므로 int push변수와 비교하여 더 작으면 push값에 대입
6. push값이 초기값에서 변화가 없다면 만들 수 없는 단어이므로 -1를 반환하고 반복문 종료
7. push값이 정상적으로 변동됐다면 answer값에 추가
8. 반복문이 끝나면 answer값을 result배열에 순서대로 대입

- 회고

3중 for문으로 시간복잡도상 매우 비효율적인 코드일거라 생각하여 ChatGPT에 질문해봤다.

import java.util.HashMap;
import java.util.Map;

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 c = key.charAt(i);
                // 해당 문자가 처음 발견되거나 더 적은 입력 수로 발견되었을 때 업데이트
                keyPressMap.put(c, Math.min(keyPressMap.getOrDefault(c, Integer.MAX_VALUE), i + 1));
            }
        }

        int[] result = new int[targets.length];
        
        // 각 타겟 문자열에 대해 최소 키 입력 수 계산
        for (int i = 0; i < targets.length; i++) {
            int answer = 0;
            for (int j = 0; j < targets[i].length(); j++) {
                char c = targets[i].charAt(j);
                if (keyPressMap.containsKey(c)) {
                    answer += keyPressMap.get(c);
                } else {
                    answer = -1; // 해당 문자가 키맵에 존재하지 않음
                    break;
                }
            }
            result[i] = answer;
        }
        
        return result;
    }
}

 

 

keyPressMap.put(c, Math.min(keyPressMap.getOrDefault(c, Integer.MAX_VALUE), i + 1))

• 해당 부분에서 각 문자에 대한 수치를 Math.min을 통해 최소값으로 map에 저장
• for문을 통해서 key의 포함여부를 확인하고 포함된다면 value값을 answer에 증가

 

- 진행

일자	완료 번호
24.07.16 ~ 24.07.31	1~63
24.08.01	64
24.08.02	65
24.08.05	66