[Programmers] 대충 만든 자판 - Java

문제

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

프로그래머스

 

풀이

이 문제를 키 배열이 있다면, 키를 누른 최소 횟수를 구하는 문제이다.

AAB ABC 라는 키 배열이 있는데, AB를 만드는 최소 횟수를 구한다고 하자.

그러면 A를 만드는데 => 1번(키배열 상관 없음),  B를 만드는데 => 첫번째 키배열에서 3번이 아니라, 두번째 키배열에서 2번을 눌러서 3번이 될 것이다.

 

즉

1. 키 배열에 있는 알파벳 대문자들 중에서 문자의 최소의 번째(인덱스 + 1)를 구한다.

2. 문자가 없다면, 만들 수 없으며(-1), 문자가 있으면 최소 번째를 계속 더해서 배열에 기록한다.

 

HashMap 사용

1. 문자의 최소 번째를 HashMap을 사용했는데, 최소 번째를 구할때, 만약에 문자가 없으면 HashMap의 getOrDefault라는 메서드를 이용해 최댓값을 리턴하도록해서, 최소 번째를 기록한다.

2. HashMap key에 만드려고 하는 문자가 없으면 -1, 문자가 있으면 값을 더해서 배열에 기록한다.

 

소스코드

import java.util.Map;Add commentMore actions
import java.util.HashMap;

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

 

int 배열 사용

1. 문자의 최소 번째를 int 배열을 사용해서 최소 번째를 구할때, 만약에 문자가 없으면 Integer.MAX_VALUE를 기록하고, 문자가 있으면 최솟값을 갱신하도록 한다.
2. 문자 인덱스에 해당하는 배열에 Integer.MAX_VALUE가 기록되어있으면, -1, 그게 아니라면 값을 더해서 배열에 기록한다.

 

소스코드

import java.util.Arrays;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int alphaCnt = 'Z' - 'A' + 1;
        int[] arr = new int[alphaCnt];
        
        Arrays.fill(arr, Integer.MAX_VALUE);
        
        for (String key : keymap) {
            for (int i = 0; i < key.length(); i++) {
                int idx = key.charAt(i) - 'A';
                
                arr[idx] = Math.min(arr[idx], i + 1);
            }
        }
        
        int[] answer = new int[targets.length];
        
        for (int i = 0; i < targets.length; i++) {
            int cnt = 0;
            
            for (char ch : targets[i].toCharArray()) {
                int idx = ch - 'A';
                
                if (arr[idx] == Integer.MAX_VALUE) {
                    cnt = -1;
                    break;
                } 
                
                cnt += arr[idx];
            }
            
            answer[i] = cnt;
        }
        
        return answer;
    }
}

 

실행 결과

HashMap 풀이 실행 결과

int 배열 실행 결과

 

풀이	평균 실행 시간(ms)	평균 메모리 용량(MB)
HashMap 사용	1.61	84.29
int[] 사용	0.34	82.15

 

실행 시간이 약 78% 빨라졌으며, 메모리 용량도 약 2% 감소했다.

그 이유는 HashTable에서 key를 저장할때, 체이닝, open-addressing과 같이 key값이 충돌할때의 값을 저장하는데 시간적인 소요가 있기 때문이다.