휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.
예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.
같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.
이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.
1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열keymap과 입력하려는 문자열들이 담긴 문자열 배열targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.
단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.
제한사항
1 ≤keymap의 길이 ≤ 100
1 ≤keymap의 원소의 길이 ≤ 100
keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.
예를 들어keymap[0]= "ABACD" 인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다.
keymap의 원소의 길이는 서로 다를 수 있습니다.
keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
1 ≤targets의 길이 ≤ 100
1 ≤targets의 원소의 길이 ≤ 100
targets의 원소는 알파벳 대문자로만 이루어져 있습니다.
입출력 예
["ABACD", "BCEFD"]
["ABCD","AABB"]
[9, 4]
["AA"]
["B"]
[-1]
["AGZ", "BSSS"]
["ASA","BGZ"]
[4, 6]
내 풀이
function solution(keymap, targets) {
const answer = [];
for (const target of targets) {
let sumOfMin = 0; // keymap에서 찾은 위치 중 가장 적은 값들의 합
for (let i = 0; i < target.length; i += 1) { // target의 알파벳을 순회
const table = Array(keymap.length).fill(); // 알파벳을 발견한 위치를 넣어줄 배열
for (let j = 0; j < keymap.length; j += 1) {
if (keymap[j].includes(target[i])) // 현재 순회중인 알파벳이 keymap에 존재하면
table[j] = keymap[j].indexOf(target[i]);
else table[j] = Number.MAX_VALUE; // 존재하지 않을 경우 무한 값을 푸시
}
sumOfMin += Math.min(...table) + 1; // keymap에서 발견한 index들 중 가장 적은 값
}
if (sumOfMin < Number.MAX_VALUE) answer.push(sumOfMin);
else answer.push(-1); // 단 하나의 알파벳이라도 찾지 못한경우 SumOfMin에는 무한값이 들어있게됨.
}
return answer;
}
1차시도에 성공했지만 반복문이 많이 들어갔기에 최선의 복잡도로 구현된 것은 아닙니다.
기본적인 알고리즘은 다음과 같이 구현했습니다.
우선 targets의 값들("ABCD", "AABB" .. )을 순회하면서 각 target들의 알파벳들을 순회합니다.
각 알파벳별로 keymap을 하나씩 확인해가며 현재 순회중인 알파벳이 각각의 keymap에 들어있는지 확인하고 들어있다면 그 위치의 index값을 table에 넣어주고 존재하지 않을 경우 MAX_VALUE를 table에 넣어줍니다. MAX_VALUE는 값을 찾지 못했다는 뜻이며 table에 들어있는 값들 중 최솟값을 구할 때 거르려는 의도입니다.
예를 들어, 첫번째 target인 ABCD의 각 알파벳을 순회하면서 변수들은 다음과 같이 값이 담기게 됩니다.
target[i]
A
B
C
D
table
[0, MAX_VALUE]
[1, 0]
[3, 1]
[4, 4]
Math.min(...table) + 1
0 + 1
0 + 1
1 + 1
4 + 1
문제에서는 0번이 아닌 한번부터 셈을 하고 있으므로 Math.min은 1씩 추가하여 더해줍니다.
따라서 ABCD의 합인 sumOfMin의 값은 target ABCD의 경우 9가 되며 두번째 target인 AABB는 같은 방식으로 4가 담기게 됩니다.
입출력 예의 두번째 케이스의 경우 target인 B는 어떤 keymap에도 들어있지 않으므로 최종 sumOfMin은 MAX_VALUE가 되고 이는 목표 문자열을 작성할 수 없다는 뜻이므로 -1이 최종값으로 들어가게 됩니다.