[해커랭크] 알고리즘을 최적화 해보자 Ransom Note

Hacker Rank - Interview Preparation Kit

category - [Hash Tables]

language - [javascript]

 

2. Ransom Note

www.hackerrank.com/challenges/ctci-ransom-note/problem

Hash Tables: Ransom Note | HackerRank

 

---

 

[문제 선정의 이유]

이게 아닌데!

알고리즘 Optimization을 연습하기 좋은 문제를 고른 것이지 납치 범죄에 가담하고 싶지 않음을 미리 밝힌다.

간단하고 쉬운 문제부터 시작해 보겠다. 

 

---

 

[문제 내용]

1. 납치범은 필적 감정을 피하기 위해 몸값 요구 노트의 단어를 전부 잡지에서 찾아 붙이고 싶다.
2. 한 단어 단위로 바꿔치기 가능하고, 단어를 스펠 단위로 잘라서 붙이는 것은 불가능하다.
3. 노트에 중복되는 단어가 있다면 잡지에도 그 단어는 중복되는 개수만큼 있어야 한다.

 

인풋은 잡지에 있는 단어 배열과 바꿔치기를 원하는 노트의 단어 배열이 들어온다.

아웃풋은 잡지의 단어들이 납치범의 모든 단어를 바꿔치기 해줄 수 있는지 "Yes" or "No"를 출력한다.

 

---

 

[문제해설 1]

(#magazine = m, #note = n)

 

이 문제를 보자마자 떠오르는 풀이법은 아마 이럴 것이다.

function checkMagazine(magazine, note) {
    for(let i=0; i<note.length; i++){
        let find = false;
        for(let j=0; j<magazine.length; j++){
            if(note[i]===magazine[j]){
                magazine.splice(j,1);
                find = true;
                break;
            }
        }
        if(!find){
            console.log("No");
            return;
        }
    }
    console.log("Yes");
}

노트의 배열을 순회하면서 나온 각 단어를 잡지 배열을 순회하며 하나하나 비교한다.

 

이렇게 풀어도 답은 나온다. 문제는 시간이다. 

이 알고리즘의 시간 복잡도는 O(m*n)이다.

 

잡지와 노트 배열의 크기가 커질수록 곱연산은 크게 증가할 것이다. 

이를 합연산으로 바꾸어 최적화를 해보자. 

 

---

 

[문제해설 2]

노트에 있는 단어 하나하나를 해시 테이블(Hash Table)에서 밸류를 찾는 키 값으로 생각하고 접근하면 어떻게 될까?

 

잡지에 있는 단어들을 키로 가지고 밸류는 단어들의 개수인 해시 테이블을 만들고.

const hash = magazine.reduce((acc,cur)=>{
    acc[cur] = (acc[cur]||0)+1;
    return acc;
},{});

(js에서는 단순 for문 보다 필요에 따라 reduce와 map 등을 적절히 활용한다면 구현도 편리하고 성능도 향상시킬 수 있다.)

 

노트의 단어를 순회하며 해시 테이블의 키에 넣어보는 것이다.

키에 해당하는 밸류가 있다면 -1을 해주어 하나 사용했음을 표기하고 다음 단어로 넘어간다.

키에 해당하는 밸류가 아예 없거나, 밸류를 이미 다 써버렸다면(단어 중복) 찾기에 실패한 것으로 판단하고 종료한다.

for(let i=0; i<note.length; i++){
    if(hash[note[i]]){
        hash[note[i]]-=1;
    }else{
        console.log("No");
        return;
    }
}

 

바꿔치기가 모두 끝난 경우 성공을 출력해주는 것 까지 추가하면 최종적으로 이렇게 구성 할 수 있다.

function checkMagazine(magazine, note) {
    const hash = magazine.reduce((acc,cur)=>{
        acc[cur] = (acc[cur]||0)+1;
        return acc;
    },{});
    for(let i=0; i<note.length; i++){
        if(hash[note[i]]){
            hash[note[i]]-=1;
        }else{
            console.log("No");
            return;
        }
    }
    console.log("Yes");
}

 

이중 반복문을 피하고 각 배열이 독립적으로 순회하였으므로 시간 복잡도는 O(m+n)이 된다.

 

---

 

여기까지 알고리즘 최적화가 모두 어렵고 복잡한 것만은 아니라는 자신감을 키워줄 수 있는 워밍업 문제를 풀어보았다.

이제 제대로 된 최적화 문제를 풀며 좌절하는 시간을 가져보자.

kline1103.tistory.com/15?category=423526

[해커랭크] 알고리즘을 최적화 해보자 Array Manipulation

---