문제 66. 대충 만든 자판 (난이도 7)

 

처음에 중첩되는 반복문이 너무 많아지는 경향을 보여서

시간 초과가 될까봐 선 뜻 알고리즘을 작성하지 못 했다...

 

그래서 여러 방법을 찾아보면서 반복 횟수를 줄여 볼려고

시도 했지만 쉽지 않았다...

 

그래서, 반복문을 줄이는 대신 keymap의 요소들에서

중복을 제거해(어차피 먼저 나오는 녀석들을 사용할거라)

중첩된 반복문에서 불 필요한 반복 횟수를 줄이는 방법으로

 

문제를 풀었다.

 

제출한 코드 : 

 

function whatTimesPushKey(mapArray, target)
{
    let sum = 0;
    for(let i = 0; i < target.length;i++)
    {
        let min = Infinity
        // 최소 몇 번 눌러야 하는지 담을 변수
        for(let j = 0; j < mapArray.length; j++)
        {
            let num = mapArray[j].get(target[i])
            // target[i] : 단어를 가져와
            // get을 이용해 key에 따른 value 가져오기
            if(!num) continue;
            // value가 없으면 스킵
            min = min > num ? num : min;
            // 있을 때 min 보다 작으면 갱신
        }
        if(min === Infinity) return -1;
        // 만약 찾고자 하는 단어가
        // 없으면 Infinity 상태 그대로일거라
        // 찾고자 하는 단어가 없으면 바로 -1로 반환
        sum += min;
        // 있으면 횟수 더해주기
    }
    return sum;
    // 횟수 반환
}
function solution(keymap, targets) {
    const answer = []
    const mapArray = []
    //keymap에 따른 각각의 Map 객체를 담을 배열
    for(let i = 0; i < keymap.length; i++)
    {
        mapArray.push(new Map())
        //keymap 개수 만큼 Map 객체 생성
        for(let j = 0; j < keymap[i].length;j++)
        {
            if(mapArray[i].get(keymap[i][j])) continue;
            // 이미 앞에 중복된 단어가 나왔다면 스킵
            mapArray[i].set(keymap[i][j],j + 1)
            // 단어를 key로, 단어의 위치를 value로 전달
        }
    }
    for(let i = 0; i < targets.length;i++)
    {
        answer[i] = whatTimesPushKey(mapArray,targets[i])
        // 타겟 배열에서 타겟과 중복 제거된 key 배열 전달
    }
    return answer
}

 

문제를 풀고 다른 사람들은 어떻게 풀었는지 코드를 확인해보니

 

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))
    // 문자열을 단어로 분리된 배열을 만들고, 
    // map함수를 사용해 단어 배열의 각 단어를
    // key로 사용하고 index를 value로 사용해
    // 저장 및 가장 작은 index 넘버로 갱신했다
    }
    for (const items of targets) {
        answer.push(items.split('').reduce((acc, item) => acc += map[item], 0) || -1)
        // targets의 요소 배열(items)을 가져와
        // 요소 배열을 단어 배열로 만든 후
        // 그 배열을 reduce로 
        // map[item]이 있으면 누산값에 더해주고,
        // || -1로 없으면 -1을 answer에 넣어준다.
    }
    return answer;
}

 

 

 

문제를 풀고 다른 사람들의 코드를 찾아보니,

 

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))
    // 문자열을 단어로 분리된 배열을 만들고, 
    // map함수를 사용해 단어 배열의 각 단어를
    // key로 사용하고 index를 value로 사용해
    // 저장 및 가장 작은 index 넘버로 갱신했다
    }
    for (const items of targets) {
        answer.push(items.split('').reduce((acc, item) => acc += map[item], 0) || -1)
        // targets의 요소 배열(items)을 가져와
        // 요소 배열을 단어 배열로 만든 후
        // 그 배열을 reduce로 
        // map[item]이 있으면 누산값에 더해주고,
        // || -1로 없으면 -1을 answer에 넣어준다.
    }
    return answer;
}

 

객체를 사용해 keymap에 나타나는 단어에서

가장 빠른 index를 저장하고,

 

reduce 함수로 targets 요소 배열에 해당하는 단어

index를 누산합 하는 식으로 문제를 해결했다.

 

아직 알고리즘이 약하다는 생각에 많이 아쉬움이 납는다.