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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

---

1. 문제 탐색

• 여러 개의 자판이 있고, 각 자판에는 알파벳이 여러 번 등장함.
• 자판의 각 알파벡이 몇 번째로 눌러야 입력되는지 주어짐
• 자판에 없는 문자는 -1 리턴.
• 주어진 문자열 targets 를 입력할 때, 각 문자별 최소 몇 번 키를 눌러야 하는지 합산해서 리턴하는 문제

 

2. 풀이 알고리즘

1) 각 알파벳의 최소 클릭 횟수 테이블 만들기 (Preprocessing)

• keymap 의 각 문자열을 탐색하여, 해당 알파벳이 몇 번째 위치에 있는지 모두 확인하고 → 가장 작은 값만 저장.

→ 시간 복잡도: O(M × L) (M = keymap 배열 길이, L = 각 문자열 길이)

 

2) 각 target 문자열을 순회하면서 누르는 횟수 계산

• 각 문자열의 문자 하나씩 보면서 1단계에서 만든 테이블에서 누르는 횟수 가져옴
• 없는 문자는 -1

→ 시간복잡도: O(N × T) (N = target 배열 길이, T = 각 target 문자열 길이)

 

---

3. 정답 코드 

import java.util.*;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        Map<Integer, Integer> alphaMap = new HashMap<>();
        List<Integer> answer = new ArrayList<>();
        int MAX_VALUE = 101;

        for (int i = 0; i < 26; i++) {
            alphaMap.put(i, 101);
        }

        for (String key : keymap){
            for (int i = 0 ; i < key.length() ; i++){
                char c = key.charAt(i);
                int index = i + 1;
                int int_char = (int) c - 'A';
                if (alphaMap.get(int_char) > index){
                    alphaMap.put(int_char, index);
                }
            }
        }

        for (String target : targets){
            int count = 0;
            for (char c : target.toCharArray()){
                int value = alphaMap.get((int) c - 'A');
                if (value == 101){
                    count = -1;
                    break;
                }
                count += value;
            }
            answer.add(count);
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

---

4. 마치며.

가장 많이 애먹었던 부분은 무엇이었을까. List의 stream() method의 사용법에 대해서 내가 빠르게 떠올리지 못한 것 같았다. java 언어에 대한 공부를 더 많이 해야겠다는 생각이 든다.