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

https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

입력

keymap - 임의의 문자열 자판이 있는 배열

targets - 입력하고 싶은 문자열이 있는 배열

 

출력

문자열마다 자판을 최소로 누르는 횟수가 담긴 배열 (문자열을 만들 수 없는 경우에는 -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의 원소는 알파벳 대문자로만 이루어져 있습니다.

풀이

가장 간단한 풀이는 반복문을 4번 중첩시켜서 활용하는 것이었다. targets 안에 문자열을 하나씩 하나씩 순회해 가면서 keymap에 그 문자가 있는지 그리고 있다면 어떤 값이 최소인지 모두 검사하면서 출력해야 할 배열에 담는 것이었다.

그러나 이는 시간 복잡도가 O(n^4)여서 바로 포기하였다.

(제한 사항에 따르면 100*100*100*100가 나온다.)

 

두 번째 방법은 사전에 모든 단어와 인덱스의 최솟값을 담고 targets을 순회하면서 값을 출력하는 방법이다. keymap을 순회하면서 dict라는 객체에 값이 없거나 값이 순회하는 인덱스보다 크다면 갱신시켜준다. 이 때 dict.set(v[i], i+1)를 활용하였다.

그러고 나서 targets을 순회하면서 dict에 값이 없다면 -1을 값이 있다면 갱신시켜서 배열에 값을 담았다.

이렇게 만든 코드는 다음과 같다.

function solution(keymap, targets) {
    var answer = [];
    const dict = new Map();
    keymap.forEach(function(v) {
        for (let i=0; i<v.length; i++) {
            if (!dict.has(v[i])||dict.get(v[i])>i+1) dict.set(v[i], i+1);
        }
    })
    targets.forEach(function(v) {
        let temp = 0;
        for (let i=0; i<v.length; i++) {
            if (!dict.has(v[i])) break;
            else temp += dict.get(v[i]);
        }
        answer.push(temp ? temp : -1)
    })
    return answer;
}

 

그러나 이렇게 만든 코드는 문제가 있었다. dict에 값이 없다면 temp = 0이라고 예상을 했는데 temp가 0이 아니어도 사전에 값이 없는 경우가 있었다.

["ABCDE"], ["DG"]를 입력하면 [-1]이 나와야 하는데 [3]이 나온다.

따라서 dict에 값이 없다면 바로 return을 하도록 코드를 수정하였다.

코드

function solution(keymap, targets) {
    var answer = [];
    const dict = new Map();
    
    keymap.forEach(function(v) {
        for (let i=0; i<v.length; i++) {
            if (!dict.has(v[i]) || dict.get(v[i])>i+1) dict.set(v[i], i+1);
        }
    })
    
    targets.forEach(function(v) {
        let temp = 0;
        for (let i=0; i<v.length; i++) {
            if (!dict.has(v[i])) return answer.push(-1);
            else temp += dict.get(v[i]);
        }
        return answer.push(temp);
    })
    return answer;
}

 

다른 사람의 풀이를 보니 단축평가를 하여 좀 더 짧게 코드를 짜셨다. 나중에 다시 리팩토링해야겠다. 하려고 했다가 실패했다.

또한 프로그래머스는 객체를 반환 값으로 넣고 실행 결과를 누르면 잘 안나온다. VSCode로 두 번 확인하자.