문제 풀기/JavaScripts

문제 66. 대충 만든 자판

kagan-draca 2024. 8. 30. 11:18

 

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

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

 

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

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

 

그래서, 반복문을 줄이는 대신 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를 누산합 하는 식으로 문제를 해결했다.

 

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

'문제 풀기 > JavaScripts' 카테고리의 다른 글

문제 68. 햄버거 만들기  (0) 2024.09.03
문제 6. 둘만의 암호  (0) 2024.09.03
문제 65번. 문자열 나누기  (0) 2024.08.29
문제 64. 체육복  (0) 2024.08.28
문제 63. 숫자 짝꿍(객체 사용 {})  (0) 2024.08.26