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

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

 

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

프로그래머스

---

Think🤔

 

LV0을 푸는데 너무 쉬워서 LV1로 넘어왔습니다.

 

주어지는 인자값은 

String [] keymap 여기서 인자값이 "ABACD" 인 경우 한번 누르면 맨 처음 A , 두번은 B 이런식

String [] targets 이 요소는 "AABB" 이런식으로 들어가 있는데 , 

keymap에 있는 키를 가지고 targets의 문자를 최소로 눌러서 작성 하는 것

 

그러면 "ABACD" , "BCEFD" 라는 키가 있으면 "ABCD"는

 

A는 1번키에서 한번 누르면 되니깐 여기서 1

B는 2번키에서 한번 누르면 되니깐 여기서 1

C는 2번키에서는 두번 누르면 되니깐 여기서 2(1번키에서는 C를 누르려면 총 4번을 눌러야 하기때문에 2번)

D는 둘다 5번씩 눌러야 되니깐 여기서 누르면 됨

 

이거를 이제 생각해보면

 

targets에 있는 요소들을 하나씩 처리해야 되니깐 일단 첫번째 요소를 가져와서

keymap에 매칭해보면서 더 가까이에 있는 keymap을 이용해서 정답에 +를 해준 후 반환하면 된다.

 

3중 for문으로 하려했으나 너무 비효율적이고 keymap의 크기와 targets의 길이가 각각 100개인 점

100의 제곱인 10000번을 돌 수 있기 떄문에 이 방법말고 다른 방법을 참조해서 해보기로 한다.

 

HashMap을 사용해서 푸신 분들을 참조하여 적용해보기로 했다.

 

HashMap을 이용해서 하면 Character형과 int형을 이용해서 해당 문자열의 값이 작은 키 패드를 먼저 만들 수 있기 떄문

 

반복문을 이용해서 대충 만든 자판을 조합하여 새로운 자판을 만든다.

 

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

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        
        int[] answer = new int[2];
        
        HashMap<Character,Integer> hs = new HashMap();
        
        for(String s : keymap){
            for(int i=0; i<s.length(); i++){
                hs.put(s.charAt(i) , Math.min(hs.get(s.charAt(i)) , hs.getOrDefault(s.charAt(i) , i)));
            }
        }
        
        return answer;
    }
}

 

여기까지 작성했는데 npe가 발생한다.. 뭐가 문젠지?

 

가독성을 위해 s.charAt(i) 는 일단 변수처리하는게 좋아보인다.

 

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

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        
        int[] answer = new int[2];
        
        HashMap<Character,Integer> hs = new HashMap();
        
        for(String s : keymap){
            for(int i=0; i < s.length(); i++){
                char key = s.charAt(i);
                
                hs.put(key , Math.min(hs.getOrDefault(key , Integer.MAX_VALUE) , i+1));
            }
        }

        System.out.print(hs);
        
        return answer;
    }
}

 

npe가 발생하는 이유는 hs.get으로 가져올려고 하나 그 값이 존재하지 않아서 못가져오기 때문이다.

 

그럼 해당 코드를 수정해서 만약에 값이 없어서 가지고 오지 못하면 지금의 값을 넣어주고

못가져오면 제일 큰 값 Integer.MAX_VALUE값을 넣어 현재의 숫자를 넣어주게 Math.min을 이용한다.

 

여기 까지 하면 일단 hs는 새로운 자판이 되었다.

 

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

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        
        int[] answer = new int[targets.length];
        
        HashMap<Character,Integer> hs = new HashMap();
        
        for(String s : keymap){
            for(int i=0; i < s.length(); i++){
                char key = s.charAt(i);
                
                hs.put(key , Math.min(hs.getOrDefault(key , Integer.MAX_VALUE) , i+1));
            }
        }
        
        for(int i=0; i<targets.length; i++){
            int cnt = 0;
            for(int j=0; j<targets[i].length(); j++){
                char key = targets[i].charAt(j);
                if(hs.containsKey(key)){
                    cnt += hs.get(key);
                }
            }
            
            if(cnt == 0){
                answer[i] = -1;
            }else{
                answer[i] = cnt;
            }
            
        }
        
        return answer;
    }
}

 

이렇게 하니 테스트 14~23번은 전부 실패한다...

 

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

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        
        int[] answer = new int[targets.length];
        
        HashMap<Character,Integer> hs = new HashMap();
        
        for(String s : keymap){
            for(int i=0; i < s.length(); i++){
                char key = s.charAt(i);
                
                hs.put(key , Math.min(hs.getOrDefault(key , Integer.MAX_VALUE) , i+1));
            }
        }
        
        for(int i=0; i<targets.length; i++){
            int cnt = 0;
            for(int j=0; j<targets[i].length(); j++){
                char key = targets[i].charAt(j);
                if(hs.containsKey(key)){
                    cnt += hs.get(key);
                }else{
                    cnt = 0;
                    break;
                }
            }
            
            if(cnt == 0){
                answer[i] = -1;
            }else{
                answer[i] = cnt;
            }
            
        }
        
        return answer;
    }
}

 

입력값 〉 ["BC"], ["AC", "BC"]
기댓값 〉 [-1, 3]

 

테스트 케이스를 추가하고 , 다른 반례를 이용해서 예외를 추가 하였다.

 

단어중에 누르는거만 생각했지 없는 값이 있으면 바로 끝내줘야 한다.

---

Solution✍

 

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

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        
        int[] answer = new int[targets.length];
        
        HashMap<Character,Integer> hs = new HashMap();
        
        for(String s : keymap){
            for(int i=0; i < s.length(); i++){
                char key = s.charAt(i);
                
                hs.put(key , Math.min(hs.getOrDefault(key , Integer.MAX_VALUE) , i+1));
            }
        }
        
        for(int i=0; i<targets.length; i++){
            int cnt = 0;
            for(int j=0; j<targets[i].length(); j++){
                char key = targets[i].charAt(j);
                if(hs.containsKey(key)){
                    cnt += hs.get(key);
                }else{
                    cnt = 0;
                    break;
                }
            }
            
            if(cnt == 0){
                answer[i] = -1;
            }else{
                answer[i] = cnt;
            }
            
        }
        
        return answer;
    }
}

---

 

Review🤩

 

굳뜨

---