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

📖 문제 설명

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

예를 들어, 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의 원소는 알파벳 대문자로만 이루어져 있습니다.

 

---

💾 입출력 예시

 

keymap	targets	result
["ABACD", "BCEFD"]	["ABCD","AABB"]	[9, 4]
["AA"]	["B"]	[-1]
["AGZ", "BSSS"]	["ASA","BGZ"]	[4, 6]

 

---

⌨️ 나의 풀이 (코드)

 

먼저 의사 코드를 통해 구현해야 하는 로직에 대해 정리해 보았다.

 

1. targets의 문자열이 만들어질 수 있는지 확인 (아니라면 -1 저장 후 다음 요소로 이동)
2. keymap을 기반으로 가장 빠르게 해당 키를 입력할 수 있는 횟수 기록 (이후 계속 누적)
3. 문자열의 끝에 도달했다면 누적값을 저장, 초기화 후 다음 요소로 이동, 반복

 

생각보다 로직이 잘 정리되지 않아서 1번의 과정만을 구현해 주어진 예시 1번을 콘솔창으로 확인해 보았다.

 

 

위를 통해 각 문자열의 영어 알파벳 당 매개변수 target의 문자열 개수만큼의 indexOf값을 받고 있음을 알 수 있었다. 따라서 해당 값들을 묶어서 비교할 필요가 있었는데, 이를 위해 비교군 역할을 할 배열을 순회마다 반환하는 .map() 함수를 활용해야겠다는 생각이 들었다.

 

 

이후 .map()을 활용해 반환된 배열 내의 가장 작은 수를 탐색해 변수에 할당하면 된다고 생각했고, Math.min() 메서드를 사용했다.

 

하지만 Math.min(keymap.map((key) => { return key.indexOf(char); })); 가 될 경우 NaN을 반환했다. Math.min() 메서드는 배열을 탐색하는 것이 아닌 주어진 매개변수들을 비교해 가장 작은 수를 반환하는 값이기 때문에 spread 연산자(...)를 활용해 .map() 메서드를 통해 생성된 배열의 요소를 얕은 복사를 통해 매개변수로 설정해줘야 했다.

 

 

한 가지 문제점을 더 발견했다.

 

위의 로직대로라면 keyIdx에 -1값이 할당되기 때문에  문제에서 제시된 "목표 문자열을 작성할 수 없을 때는 -1을 저장"한다는 조건에 맞지 않고, 이는 곧 문자열 내에서 원하는 값을 찾지 못했다는 뜻으로 왜곡된다. (예시에서 target "ABCD"의 "A" 문자는 keymap "ABACD"에 포함되어  있지만 -1값을 반환하고 있다.)

 

 

이전 단계로 돌아와서, 만약 인덱스 값이 문자열 내에 존재하지 않는다면 (key.indexOf(char)이 -1 값이라면) 큰 수 1000을 반환해 더 작은 값을 가져오도록 로직을 수정했다. 숫자 1000을 반환하는 이유는 제한 사항에서 "target의 원소의 길이가 1 ~ 100 사이"라고 했기 때문에 100보다 더 큰 수, 안전하게 1000을 설정했다.

 

정상적으로 반환되는 index값

 

위의 과정이 모두 잘 작동되고 있는 것을 확인한 후, 각 버튼이 몇 번 눌렸는지 확인하기 위한 변수 pressed (count 역할)와 눌렀던 버튼 수를 매 순회마다 기록하고 저장할 수 있도록 answer 배열을 선언 및 할당 후, .push() 메서드를 통해 추가했다.

 



기본 테스트를 통과하지 못했다.

 

일치하는 문자 keymap 내에 없을 때를 고려하지 못했기 때문이다. 

 

function solution(keymap, targets) {
  const answer = [];

  targets.forEach((target) => {
    let pressed = 0;
    for (const char of target) {
      const keyIdx = Math.min(
        ...keymap.map((key) => {
          if (key.indexOf(char) === -1) {
            return 1000;
          } else {
            return key.indexOf(char);
          }
        })
      );
      if (keyIdx === 1000) {
        pressed = -1
        break;
      } else {
        pressed += keyIdx + 1;
      }
    }
    answer.push(pressed);
  });

  return answer;
}

 

이에 따라 로직을 수정했고 (만약 수가 1000이라면 pressed값을 -1로 반환, 순회도 종료하도록), 모든 테스틑 통과할 수 있었다.

 

---

📝 Note

 

문제를 푸는 과정에서 두 가지 의문이 들었는데, 다른 사람의 코드를 통해 의문점을 해소할 수 있었다.

 

1. Math.min()을 활용하지 않고 .reduce()를 활용해 가장 작은 값을 구하는 방법이 있지 않나?

function solution(keymap, targets) {
    const answer = [];
    const map = {}
    for (const items of keymap) {
        items.split('').map((item, index) => map[item] = (map[item] < index+1 ? map[item] : index+1))
    }
    for (const items of targets) {
        answer.push(items.split('').reduce((cur, item) => cur += map[item], 0) || -1)
    }
    return answer;
}

 

단번에 코드가 이해되지 않았기에 코드를 하나하나 분석해 보았다. 

 

--- for (const items of keymap) ---
1) keymap 배열을 순회해 map 객체 안에 각 문자의 번호를 입력
2) 현재 선택된 문자가 중복된다면 더 작은 (적게 누를 수 있는) 값으로 변경
--- for (const items of targets) ---
3) targets 배열을 순회, 이 때 각 문자열의 문자를 1)과 같이 순회, 미리 저장된 map 객체 내의 문자(키)로 지정된 값을 확인
4) 확인된 값을 추가 (단, falsy한 값이라면 -1로 변경)

 

보다 잘 이해하기 위해 콘솔창으로 확인해 보았다.

 

 

실질적으로 reduce 과정에서 최소값을 구한 건 아니지만, 해당 코드에서 사용한 삼항 연산자의 로직을 통해 reduce에서도 같이 사용할 수 있는 것을 알 수 있었다.

 

2. 제한사항 targets, keymap의 길이가 더 커진다면?

 

대부분 이에 대한 해결책으로 Infinity 객체를 사용하는 것 같다.

 

Inifinity 전역 객체는 말 그대로 무한대를 나타내는 숫자 값이다. 만약 Inifity와 어떤 수를 Math.min() 메서드를 통해 비교한다면 비교하는 다른 수가 더 적은 값으로 반환되기 때문에 이전에 사용했던 1000으로 비교하는 것보다 명확하고 안전한 방법임을 알 수 있다.

 

---

🔖 참고

 

최댓값과 최솟값: https://developer-talk.tistory.com/159

[JavaScript]배열에서 최댓값(max), 최솟값(min) 구하기

Inifiy 객체: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Infinity

Infinity - JavaScript | MDN

논리연산자 ||의 원리: https://curryyou.tistory.com/193

[자바스크립트] 논리연산자(&&, ||) 단축평가