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

문제 설명

임의로 설계된 휴대폰 자판이 주어질 때, 특정 문자열을 작성하기 위해 키를 최소 몇 번 눌러야 하는지 계산하는 문제입니다.

• 각 키는 여러 문자를 포함하며, 특정 키를 연속으로 누를 때마다 다음 문자로 넘어갑니다.
• 작성할 수 없는 문자열이 있는 경우 결과는 -1로 표시합니다.

---

제한사항

1. keymap 배열
   • 1 ≤ keymap.length ≤ 100
   • 1 ≤ keymap[i].length ≤ 100
   • 각 원소는 알파벳 대문자로만 구성되며, 같은 문자가 중복될 수 있습니다.
2. targets 배열
   • 1 ≤ targets.length ≤ 100
   • 1 ≤ targets[i].length ≤ 100
   • 각 원소는 알파벳 대문자로만 구성됩니다.

---

해결 방법

알고리즘: 배열을 활용한 효율적 탐색

1. 데이터 구조 초기화
   각 알파벳의 최소 키 입력 횟수를 저장할 배열 alp를 생성합니다.
2. 자판 정보 처리
   keymap을 순회하며 각 키에 할당된 문자의 최소 입력 횟수를 갱신합니다.
3. 목표 문자열 순회
   targets를 순회하며 각 문자열에 대해 필요한 총 키 입력 횟수를 계산합니다.
   작성할 수 없는 문자가 포함된 경우 -1을 결과로 추가합니다.
4. 결과 반환
   각 목표 문자열의 키 입력 횟수를 배열로 반환합니다.

---

시간 복잡도

• 자판 배열 처리: O(m⋅k)
• 목표 문자열 처리: O(t⋅n)
• 총 시간 복잡도: O(m⋅k+t⋅n)

---

구현 코드

function solution(keymap, targets) {
  let alp = new Array(26).fill(Infinity);

  for (const keyArr of keymap) {
    [...keyArr].forEach((key, index) => {
      const pos = key.charCodeAt(0) - 65;
      alp[pos] = Math.min(alp[pos], index + 1);
    });
  }

  return targets.map((keyArr) => {
    let total = 0;

    for (key of keyArr) {
      const pos = key.charCodeAt(0) - 65;
      if (alp[pos] === Infinity) return -1;
      total += alp[pos];
    }

    return total;
  });
}