[Programmers] 대충 만든 자판 : HashMap 활용하기

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다. 예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.

같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.

이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요. 단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

---

처음에 어떻게 풀지 아이디어를 잡는 데까지 상당한 시간이 걸렸다. 해쉬맵을 그렇게 다뤘는데도 불구하고… 😭 문제를 보고 내가 고민했던 부분은 이러했다. 

TRY #1. targets 만큼 for문을 돈다. 문자열 targets[i]를 순서대로 읽으면서, 현재 참조하고 있는 targets[i]의 j번째 문자가 keymap의 어디에 존재하는지 찾아낸다.

 

▶️ 하지만 '어디에 존재하는지'는 어떻게 찾아낼 것인가? keymap에도 인덱스를 부여해 keymap[p][q]와 targets[i][j]를 비교하겠다는 소리야? 4중 for문이라는 발칙한 짓까지 하고 나서야 뭔가 잘못됐음을 직감하고 모든 코드를 지웠다. 뭔가 쉬운 방법이 있을텐데….

TRY #2. 다시 원점으로 돌아왔다. 하지만, 이 문제를 해결하기 위해서는 여전히 targets[i]의 j번째 문자가 keymap 어디에 존재하는지 알아내야 한다고 생각했다. 그래서 시도한 두 번째 방법은 이러했다 : 길이가 N개인 keymap이 주어진다면, 우리는 keymap[0][0], keymap[1][0]… keymap[N-1][0]을 동시에 비교할 수 있다. 그렇다면 queue를 사용해서 앞에서부터 잘라준ㄷㅏㅁㅕㄴ…

▶️ 어쨌거나 N개의 queue를 만들어줘야 한다는 점에서 TRY#1과 하등 다를 바 없었다. 결국 난 여전히 원점이었다. 배열이나 queue나… 도대체 어떤 점에서 개선된다고 착각한거지? ;; 나 자신에게 조금 실망스러운데…?

TRY #3. 결국 사고 방식에 약간의 전환을 주고 나서야 문제를 풀 수 있었다. 아이디어는 이러하다 : 

 

1. 문자마다 '최단 거리'가 존재한다. 이 정보를 keymap 배열을 돌면서 추출해낸다. targets을 확인할 때 각 문자의 '최단 거리'가 몇인지 계속 검색해줄 것이기 때문에, 검색 속도가 배열에 비해 압도적으로 빠른 Hashmap을 사용했다. 

▶️ '입력으로 이미 존재하는 key 값이 들어온다면, 더 낮은 value를 갖을 때만 Hashmap에 저장한다'는 예외처리를 반드시 해주어야 한다.

 

2. targets만큼 for문을 돈다. 문자열 targets[i]를 순서대로 읽으면서, 현재 참조하고 있는 targets[i]의 j번째 문자의 최단 거리가 몇인지 알아내기 위해 hashmap에 검색한다. 만약 hashmap에 j번째 문자가 없다면, 입력할 수 있는 자판이 없다는 뜻이므로 -1을 리턴한다. 

---

🔽 제출한 코드 & 코드 리뷰

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(int i = 0; i < keymap.length; i++){
            for(int j = 0; j < keymap[i].length(); j++){
                if(!map.containsKey(keymap[i].charAt(j)) || j+1 < map.get(keymap[i].charAt(j)))
                   map.put(keymap[i].charAt(j), j+1);
            }
        }
        
        for(int i = 0; i < targets.length; i++){
            for(int j = 0; j < targets[i].length(); j++){
                if(map.containsKey(targets[i].charAt(j))){
                    answer[i] += map.get(targets[i].charAt (j));
                }else{
                    answer[i] = -1;
                    break;
                } 
            }
        }
        
        return answer;
    }
}

15번째 줄에서 map.get() 함수를 호출할 때, getOrDefault() 함수를 사용해보면 더욱 간단하게 코드를 작성할 수 있습니다. 이 함수는 찾으려는 key 값이 map에 존재하지 않을 때, 기본 값을 반환하는 함수입니다. 이 함수를 사용하면 15번째 줄을 다음과 같이 변경할 수 있습니다.

answer[i] += map.getOrDefault(targets[i].charAt(j), -1);​

그 외에는 크게 문제가 없어 보입니다. 전체적으로 코드 스타일이 깔끔하고 가독성이 좋습니다!

GPT한테 칭찬을 받았다… (고마워라) 하지만 이번만큼은 GPT의 조언이 무용했다. 그 이유는…

 

지피티, 그렇게 수정하면 map에 key값이 존재하지 않을 때 -1로 반환할 수 없지 않을까? 나는 answer[i]가 map에 존재하지 않으면 answer값이 -1인 채로 리턴하고 싶어. 하지만 코드를 그렇게 수정하면 answer[i] = answer[i] -1 이 되는 걸

맞아요. 수정한 코드에서는 map.containsKey 조건이 false인 경우에도 answer[i]에 이미 값이 있으면 그 값을 -1로 변경해버리기 때문에, -1로 처리할 수 없습니다.

그렇다면 이 문제를 해결하기 위해서는 map.containsKey 조건이 false인 경우에 answer[i] 값을 -1로 초기화해주는 방법이 있습니다. 이렇게 하면 answer[i]가 이미 값이 있어도 -1으로 갱신될 것입니다.

 

그래서 조언에 따라 코드를 수정하진 않았지만, 내가 자꾸 map.getOrDefault( )을 활용하지 않고 있다는 점을 상기시켜준 것은 고마웠다. 다음 번에 Hashmap 쓸 때는 꼭 써먹어야지 😶

---

프로그래머스 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스