문제설명
휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.
예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.
같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.
이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.
1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.
단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.
| keymap | targets | result |
|---|---|---|
| ["ABACD", "BCEFD"] | ["ABCD","AABB"] | [9, 4] |
| ["AA"] | ["B"] | [-1] |
| ["AGZ", "BSSS"] | ["ASA","BGZ"] | [4, 6] |
입출력 예 #1
"ABCD"의 경우,
1번 키 한 번 → A
2번 키 한 번 → B
2번 키 두 번 → C
1번 키 다섯 번 → D
따라서 총합인 9를 첫 번째 인덱스에 저장합니다.
"AABB"의 경우,
1번 키 한 번 → A
1번 키 한 번 → A
2번 키 한 번 → B
2번 키 한 번 → B
따라서 총합인 4를 두 번째 인덱스에 저장합니다.
결과적으로 [9,4]를 return 합니다.입출력 예 #2
"B"의 경우, 'B'가 어디에도 존재하지 않기 때문에 -1을 첫 번째 인덱스에 저장합니다.
결과적으로 [-1]을 return 합니다.입출력 예 #3
"ASA"의 경우,
1번 키 한 번 → A
2번 키 두 번 → S
1번 키 한 번 → A
따라서 총합인 4를 첫 번째 인덱스에 저장합니다.
"BGZ"의 경우,
2번 키 한 번 → B
1번 키 두 번 → G
1번 키 세 번 → Z
따라서 총합인 6을 두 번째 인덱스에 저장합니다.
결과적으로 [4, 6]을 return 합니다.
🤔생각해보기
우선 keymap의 배열을 돌면서, '문자-위치'를 어딘가에 저장하고, 동일한 문자가 나오면 최솟값으로 교체한다. 그리고 target을 돌면서 문자의 위치를 찾아 answer에 더해주면 될 것 같다.
👩🏻💻코드 작성해보기
import java.util.*;
class Solution {
public int[] solution(String[] keymap, String[] targets) {
int[] answer = new int[targets.length];
Map<String, Integer> map = new HashMap<>();
Arrays.stream(keymap).forEach(key -> {
String[] keys = key.split("");
Arrays.stream(keys).forEach(k -> {
int n = key.indexOf(k) + 1;
if (map.get(k) == null || map.get(k) > n) {
map.put(k, n);
}
});
});
for (int i = 0; i < targets.length; i++) {
String[] tg = targets[i].split("");
for(String k : tg) {
if(!map.containsKey(k)) {
answer[i] = -1;
break;
}
answer[i] += map.get(k);
}
}
return answer;
}
}💬설명해보기
스트림을 통해 keymaps의 값(문자열)을 하나씩 꺼낸다. 문자의 위치를 찾아야하므로 문자열을 하나씩 분리(split 사용)해준다. 스트림을 통해 문자가 담긴 배열에서 값을 하나씩 꺼낸다. 이때 '문자-위치'의 형태로 저장하면 좋을 것 같다. 이는 key-value의 형태이므로 Map 컬렉션을 사용해 저장한다. 이미 key값이 존재한다면 value의 값이 더 작을때만 저장을 한다.
targets배열을 돌면서 문자열을 하나씩 꺼내고, 배열로 만들어준다. 이 배열에서 문자를 하나씩 꺼내고 Map에 key값으로 있는지 확인한다. key값이 없으면 answre에 -1을 담는다. 아니라면 (해당 key의) value를 answer에 담는다.
---
🎙️후기
지난번 시간초과를 겪은 후 '반복문이 필요하면 stream을 활용해야지!'라는 생각이 머릿속을 가득 채웠다.
그래서 처음에는 다음과 같은 코드를 작성해 target을 찼았다. 아직 스트림의 고수가 아닌지라 스트림 안에 반복문을 두번이나 사용했다. 스트림을 사용했다고 말하기 민망할정도다... 코드만 길어지고...
함께 공부하는 분들이 우선 for문으로작성해보고, 시간초과되면 그때 바꾸는것도 나쁘지 않다고 의견을 주었다. 그래서 for문으로 바꾸고, 코드를 정리하다보니 최종 코드에 도달하게 되었다.
맨 처음 작성한 코드보다 양도 줄고, 가독성도 좋아졌다.
스트림을 사용한 첫번째 코드도 통과는 되었으니... 좋은 시도였다고 생각한다!
🛠️이전 코드
- 1차 : 스트림 활용하고 싶다!
Arrays.stream(targets).forEach(
target -> {
int sum = 0;
String[] tg = target.split("");
Stack<Integer> st = new Stack<>();
Arrays.stream(tg).forEach(
t -> {
if(map.containsKey(t))
st.push(map.get(t));
}
);
for(String a : tg) {
if(st.size()==0) {
sum = -1;
break;
}
sum += st.pop();
}
for(int i=0; i<targets.length; i++) {
if(answer[i]==0) {
answer[i] = sum;
break;
}
}
}
);- 2차 : 스트림 -> for
for (int i = 0; i < targets.length; i++) {
String[] tg = targets[i].split("");
Stack<Integer> st = new Stack<>();
Arrays.stream(tg).forEach(t -> {
if (map.containsKey(t))
st.push(map.get(t));
});
for (String a : tg) {
if (st.size() == 0) {
answer[i] = -1;
break;
}
answer[i] += st.pop();
}
}