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

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

프로그래머스

문제

매 키당 할당된 값들의 집합인 keymap, 입력하고 싶은 대상의 집합인 targets가 주어지며,

각 target당 최소 입력 횟수를 담은 int[]{targets[0] typecount , targets[1] typecount, ....} 를 반환하라.

단 매칭되는 키가 없으면 입력횟수는 -1로 간주.

 

최초접근

targets를 for문처리 하며 매 keyword당 keymap을 순회하며 매칭되는 idx를 찾고

매칭위치 +1을 횟수에 더하거나 더 앞에 있는 키를 만나면 빼는 방식으로 로직을 구성해 보았다.

 

public int[] solution(String[] keymap, String[] targets) {
		int[] answer = new int[targets.length];
        
        for(int i = 0; i < targets.length; i++){
            String target = targets[i];
            int lastKeyCharIdx = 0;
            int inputCount = 0;
            for(int j = 0; j< target.length(); j++ ){
                for(String key : keymap){
                    int idx = key.indexOf(target.charAt(j));
                    if(idx == -1) continue;
                    else if(lastKeyCharIdx >= idx){
                        if(idx == 0) inputCount ++;
                        else inputCount += (lastKeyCharIdx +1);
                    } else {
                        inputCount -= (lastKeyCharIdx +1);
                        inputCount += (idx +1);
                    }
                    lastKeyCharIdx = idx;
                }
            }
            answer[i] = inputCount == 0 ? -1 : inputCount;
        }
        
        return answer;
    }

 

수정

그러나 코드테스팅 결과 예외가 발생하였고 gpt의 도움으로 아래와 같은 문제점을 알 수 있었다.

코드의 문제점 분석 및 수정 방향

1. lastKeyCharIdx를 사용한 계산 방식이 비효율적이고 오류 가능성이 있음

현재 코드에서는 lastKeyCharIdx를 사용하여 입력 횟수를 조정하는데, 여러 키맵이 존재할 경우 제대로 작동하지 않을 가능성이 큼. 예를 들어, 키맵이 ["ABCD", "BCDA"]이고 target이 "D"일 때, D의 최적의 입력 위치를 찾기 어려움.

2. target의 각 문자가 최소 입력 횟수를 가지는 키맵을 찾는 로직이 없음

한 target의 문자(target.charAt(j))를 keymap의 여러 키에서 찾아야 하지만, 단순히 indexOf()를 사용해 탐색하면 최소 입력 횟수를 제대로 고려하지 못함. 따라서 각 문자를 입력하는 최적의 키보드 입력 횟수를 찾아야 함.

 

이를 처리하기 위한 방법으로 각 문자 별 최소 입력 횟수를 미리 계산해 map에 담고

target별 총 입력횟수를 계산하는 방식으로 수정하게 되었다.

 

최종코드

public int[] solution(String[] keymap, String[] targets) {
        int[] answer = new int[targets.length];
        Map<Character, Integer> minPress = new HashMap<>(); //각 키별 최소 입력 횟수 맵
        for(String key : keymap){
            for(int i = 0; i < key.length(); i++){
                char c = key.charAt(i);
                minPress.put(c, Math.min(minPress.getOrDefault(c,Integer.MAX_VALUE), i +1));
            }
        }

        for(int i = 0; i < targets.length; i++){
            String target = targets[i];
            int inputCount = 0;
            boolean typable = true;

            for(char c : target.toCharArray()){
                if(!minPress.containsKey(c)){
                    typable = false;
                    break;
                }
                inputCount += minPress.get(c);
            }
            answer[i] = typable ? inputCount : -1;
        }

        return answer;
    }

 

새로 알게된 것

map을 활용하여 보다 효율적인 연산의 예시.

 map.getOrDefault(키, defaultVal)의 존재와 사용예시를 알 수 있었다.

그리고 String을 char로 쪼갤 때 toCharArray()를 활용하면 보다 간단하게 결과를 얻을 수 있다는 것도 알게 되었다.