[Lv.1] 대충 만든 자판 : Java

프로그래머스

 

 

 

이해하기

처음 풀었던 코드로는 23개의 테스트 중 13개만 통과하였다...

내가 처음 접근했던 방법은 아래와 같다.

1. targets[i]를 char 배열로 받아온다.
2. char 배열을 하나하나 돌면서
   • keymap 배열 중 해당 char 를 contain 한 배열의 인덱스를 list에 저장한다.
   • list.size()만큼 for문을 돌면서 Math.min으로 가장 작은 인덱스 값을 idx로 받아온다.
   • 만약 idx가 초기 설정값인 101과 같다면 answer[i] = -1
   • 아니라면 answer[i] = idx + 1

이렇게 풀이하면 for문을 3중 또는 그 이상으로 돌려야 하기에 시간도 오래 걸린다.

실패했던 테스트 코드는 최대 n백ms 까지 나왔던 것 같다.

결과적으로 잘못된 방법... :)

 

다른 글들을 참고하며 다시 풀이해보았다.

 

 

문제풀이

import java.util.*;

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

        for (int i = 0; i < keymap.length; i++) {
            for (int j = 0; j < keymap[i].length(); j++) {
                char key = keymap[i].charAt(j);
                if (keypad.containsKey(key)) {
                    int value = keypad.get(key);
                    keypad.put(key, Math.min(value, j + 1));
                } else {
                    keypad.put(key, j + 1);
                }
            }
        }

        for (int i = 0; i < targets.length; i++) {
            int result = 0;
            boolean flag = true;
            for (char c : targets[i].toCharArray()) {
                if (keypad.containsKey(c)) {
                    result += keypad.get(c);
                } else {
                    flag = false;
                }
            }
            answer[i] = flag ? result : -1;
        }

        return answer;
    }
}

 

이 코드의 핵심은 keypad 만들기이다.

첫번째 예시인 {"ABACD", "BCEFD"}를 가지고 keypad를 만들면 다음과 같다.

1. "ABACD"를 가지고 keypad를 만든다.
   1. keypad {{A, 1}, {B, 2}, {C, 4}, {D, 5}}
   2. 이 때 A는 1, 3 두 가지 값을 가지는데 Math.min()으로 더 작은 값을 넣어준다.
2. "BCEFD"를 가지고 keypad를 수정한다.
   1. keypad {{A, 1}, {B, 1}, {C, 2}, {D, 5}, {E, 3}, {F, 4}}
   2. B와 C는 더 작은 값으로 수정한다.
   3. E와 F는 새로 추가해준다.

 

이제 이 keypad를 가지고 인덱스 값을 계산하면 된다.

만약 keypad가 해당 문자를 가지고 있지 않다면 flag를 false로 한 후 삼항 연산자를 사용하여 -1를 answer[i]에 넣어준다.

 

 

이렇게 정리할 생각을 하지 못했어서 신기한 방법이었다!

역시 자료구조를 잘 알아야... 문제도 쉽게 풀리는 것 같다.

자료구조 관련 문제를 더 많이 풀어봐야겠다.

 

 

 

 

---

 

프로그래머스 - 대충 만든 자판 (자바, JAVA)