[알고리즘] 대충 만든 자판

My Github Repository for Solution Code

https://github.com/ginsengcandy/Coding-Test-Practice/commit/bc3feaf18f791bba8177c98efa4a3cf632bbbcc2

[level 1] Title: 대충 만든 자판, Time: 3.10 ms, Memory: 85.2 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@bc3feaf

 

Problem Source

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

프로그래머스

 

Key Takeaways

1. 메서드만 private으로 분리한다고 객체지향이 아니다. private 접근 제어자는 테스트를 불가능하게 한다.

2.  문제를 읽는 사람이 타입 선언만 봐서 의미를 알 수 없다면, 별도 클래스나 타입 별칭으로 추상화하는 것이 더욱 객체지향적이다.

3. Map이 특정 키를 가지고 있는지 판단할 때는 containsKey(key)를 사용한다. contains()는 Set 전용 메서드다.

4. 배열을 원소로 초기화할 때는 중괄호까지, 길이로 초기화할 때는 대괄호만을 사용한다.

 

Problem

문제 설명
휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

제한사항
1 ≤ keymap의 길이 ≤ 100
1 ≤ keymap의 원소의 길이 ≤ 100
keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다. 예를 들어 keymap[0] = "ABACD" 인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다.
keymap의 원소의 길이는 서로 다를 수 있습니다.
keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
1 ≤ targets의 길이 ≤ 100
1 ≤ targets의 원소의 길이 ≤ 100
targets의 원소는 알파벳 대문자로만 이루어져 있습니다.

My Solution

import java.util.*;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int[] answer = new int[targets.length];
        Map<Character, Integer> shortestKeyMap = convert(keymap);
        for(int i = 0; i < targets.length; i++) {
            answer[i] = count(shortestKeyMap, targets[i]);
        }
        return answer;
    }
    
    // 최단 클릭 수를 저장한 맵과 문자열을 받아 필요한 총 클릭 수를 반환
    private int count(Map<Character, Integer> shortestKeyMap, String str) {
        int count = 0;
        char key;
        for(int i = 0; i < str.length(); i++) {
            key = str.charAt(i);
            if(shortestKeyMap.containsKey(key)) {
                count += shortestKeyMap.get(key);
            }
            else return -1;
        }
        return count;
    }
    
    // 문자열 배열을 받아 문자별로 최단 클릭 수를 저장한 맵 반환
    private Map<Character, Integer> convert(String[] keymap) {
        Map<Character, Integer> shortestKeyMap = new HashMap<Character, Integer>();
        for(String str : keymap) {
            int i = 1;
            char key;
            while(i <= str.length()) {
                key = str.charAt(i-1);
                if(shortestKeyMap.containsKey(key)) {
                    Integer value = shortestKeyMap.get(key);
                    shortestKeyMap.replace(key, Math.min(value, i));
                }
                else {
                    shortestKeyMap.put(key, i);
                }
                i++;
            }
        }
        
        return shortestKeyMap;
    }
}
/*
우리는 특정 문자열을 만들 수 있는지, 만들 수 있다면 몇 번의 클릭이 필요한지만 알면 된다.
1번 케이스의 키맵을 키별 가장 짧은 클릭 수로 정리하면
(A,1), (B,1), (C, 2), (D, 5), (E, 3), (F, 4)다.
ABCD라는 문자열을 만들기 위해 필요한 값은 1 + 1 + 2 + 5 = 9다.
따라서 키맵에 들어있는 데이터를 가지고 키별 가장 짧은 클릭 수와 매핑하는 새로운 키맵만 만들 수 있으면 된다.
abacd를 순회하며 키맵에 추가한다.
i = 1로 초기화한다
첫번째 문자를 순회한다. 키맵에 a가 없다. (a,1)을 추가한다. 1은 i값이다.
i = i + 1로 업데이트한다.
다음 문자를 순회한다. 키맵 b가 없다. (b, 2)을 추가한다. 2는 i값이다.
다음 문자를 순회한다. 키맵에 a가 있다. value값(1)과 i를 비교한다. 더 작은 값으로 대체한다. 
더이상 순회할 문자가 없으면 i를 1로 초기화한다.
다음 문자열로 넘어간 뒤 반복한다.
더이상 순회할 문자열이 없으면 종료하고 키맵을 반환한다.
*/

Performances

Memory Usage : 85.2MB

Time : 3.10ms

Strengths:

책임 분리 (SRP)가 명확합니다. solution, convert, count 세 메서드로 역할을 분리한 것은 이 페이지에서 확인한 다른 풀이들과 비교했을 때 확실히 돋보이는 부분입니다. 대부분의 다른 풀이들은 모든 로직을 solution 하나에 몰아넣고 있습니다. 메서드마다 주석으로 역할도 명시했고, 메서드명도 행위를 명확히 나타냅니다.

Limitations (or Trade-offs):

private 메서드가 클래스 설계 의도를 충분히 표현하지 못합니다. convert와 count가 private이라 외부에서 재사용할 수 없고, 테스트도 불가능합니다. 메서드를 분리한 의미를 살리려면 단위 테스트 가능성까지 고려한 접근 제어 설계가 필요합니다.

Map<Character, Integer>의 의미가 코드 외부에 드러나지 않습니다. 이 맵이 "문자별 최소 클릭 수"라는 도메인 개념을 담고 있는데, 단순히 Map으로 관리되다 보니 코드를 읽는 사람이 타입 선언만 봐서는 의미를 알 수 없습니다. 예를 들어 이를 ShortestKeyMap이라는 별도 클래스나 타입 별칭으로 추상화했다면 더 객체지향적이었을 것입니다.

convert 메서드명이 다소 모호합니다. "무엇을 무엇으로 convert하는가"가 이름만으로 드러나지 않습니다. buildShortestKeyMap 정도가 의도를 더 명확히 전달합니다.

Overall

코딩테스트 풀이 수준에서는 상위권입니다. 다른 사람 풀이 대부분이 solution 하나에 이중/삼중 for문을 욱여넣은 것과 달리, 로직의 흐름이 읽기 쉽게 구성되어 있습니다.
다만 "객체지향"의 핵심인 추상화와 캡슐화 측면에서는 아직 절차적 코드를 메서드로 잘라 놓은 수준에 가깝습니다. 완전한 OOP를 적용하려면 도메인 개념(KeyMap, Target 등)을 클래스로 모델링하는 단계까지 가야 하지만, 그것은 이 문제의 규모에서는 오히려 과설계(over-engineering)입니다. 주어진 문제 규모에 맞게 적절한 수준의 설계를 선택한 것은 맞는 판단입니다.

Problems I Met

1. IndexOutOfBoundsException 발생

문제 코드

import java.util.*;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int[] answer = new int[]{targets.length};
        Map<Character, Integer> shortestKeyMap = convert(keymap);
        for(int i = 0; i < targets.length; i++) {
            answer[i] = count(shortestKeyMap, targets[i]);
        }
        return answer;
    }
    
    // 최단 클릭 수를 저장한 맵과 문자열을 받아 필요한 총 클릭 수를 반환
    private int count(Map<Character, Integer> shortestKeyMap, String str) {
        int count = 0;
        char key;
        for(int i = 0; i < str.length(); i++) {
            key = str.charAt(i);
            if(shortestKeyMap.containsKey(key)) {
                count += shortestKeyMap.get(key);
            }
            else return -1;
        }
        return count;
    }
    
    // 문자열 배열을 받아 문자별로 최단 클릭 수를 저장한 맵 반환
    private Map<Character, Integer> convert(String[] keymap) {
        Map<Character, Integer> shortestKeyMap = new HashMap<Character, Integer>();
        for(String str : keymap) {
            int i = 1;
            char key;
            while(i <= str.length()) {
                key = str.charAt(i-1);
                if(shortestKeyMap.containsKey(key)) {
                    Integer value = shortestKeyMap.get(key);
                    shortestKeyMap.replace(key, Math.min(value, i));
                }
                else {
                    shortestKeyMap.put(key, i);
                }
                i++;
            }
        }
        
        return shortestKeyMap;
    }
}

원인: 잘못된 배열 초기화 방식

설명: 배열 초기화 방식은 원소로 초기화하는 방법과 길이로 초기화하는 방법이 있는데, 나는 길이로 초기화하고자 했으나 실제론 원소로 초기화하는 방식을 사용했다.

나의 의도는 String[] targets의 길이, 즉 원소의 수만큼 int[] answer를 초기화하는 것이었다. 그러려면 다음과 같이 코드를 작성해야 했다.

int[] answer = new int[targets.length()];

하지만 실제로는 아래와 같이 작성했다.

int answer = new int[]{targets.length()};

이 코드는 answer 배열을 targets의 실제 길이와 상관없이 항상 숫자 1개로 초기화시킨다. targets의 실제 길이가 1이라면 [1], 100이라면 [100]으로 초기화하는 것이다. targets의 길이만큼 0으로 초기화시키려던 내 의도에 벗어나게 된다.

이 코드가 IndexOutOfBoundsException을 발생시킨 이유는, 항상 길이가 1인 answer에 for문이 동작하면서 answer[1]에 접근하려고 하기 때문이다.

for(int i = 0; i < targets.length; i++) {
            answer[i] = count(shortestKeyMap, targets[i]); // answer[1]은 존재하지 않음!
        }

따라서, 배열의 초기화 방법의 차이를 잘 알아야겠다.

---

Alternative Approaches

import java.util.*;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int[] answer = new int[targets.length];
        HashMap<Character,Integer> map = new HashMap<>();

        for (String key : keymap) {
            for (int j = 0; j < key.length(); j++) {

                char ch = key.charAt(j);

                if (map.containsKey(ch)){
                    if(map.get(ch)>j){
                        map.replace(ch,j+1);
                    }
                }else{
                    map.put(ch,j+1);
                }
            }
        }

        for(int i=0; i< targets.length;i++){
            int sum = 0;
            for(int j=0; j<targets[i].length();j++){

                char ch = targets[i].charAt(j);

                if(map.containsKey(ch)){
                    sum+=map.get(ch);
                }else{
                    sum = -1;
                    break;
                }
            }
            answer[i] = sum;
        }

        return answer;
    }
}

 

References

https://8156217.tistory.com/60#google_vignette

[java] HashMap 사용법 및 예제 총정리