[리트코드] 383. Ransom Note

문제

주어진 문자열 두 개에서 하나(magazine)의 요소들로 다른 하나(ransomNote)를 만들 수 있는지 boolean으로 출력하면 되는 문제이다.

해설 코드 I

첫 번째 시도로는 두 문자열에 대해 Index를 잡아서 같으면 ransomNote의 다음 요소를 검사하고, 다르면 magazine의 Index만을 높여서 검사하는 식으로 했다.

var canConstruct = function(ransomNote, magazine) {
    let ransomArr = ransomNote.split("")
    let magazineArr = magazine.split("")
    ransomArr.sort()
    magazineArr.sort()
    let ransomIdx = 0
    let magazineIdx = 0
    while (ransomIdx < ransomArr.length && magazineIdx < magazineArr.length){
        if (ransomArr[ransomIdx] == magazineArr[magazineIdx]){
            ransomIdx += 1
            magazineIdx += 1
        } else {
            magazineIdx += 1
        }
    }
    if (ransomIdx == ransomArr.length){
        return true
    } else {
        return false
    }
};

결과 I

그런데 생각보다 시간이 많이 나옴...
다른 방법으로 도전해봐야겠다.

해설 코드 II

알고리즘 분류를 보고 생각해낸 다른 방식, 해시 테이블을 이용한 코드이다.

var canConstruct = function(ransomNote, magazine) {
    let ransomArr = ransomNote.split("")
    let magazineArr = magazine.split("")
    let ransomObj = {}
    let magazineObj = {}

    // 각각의 값들에 대한 해시 테이블 생성
    ransomArr.forEach(function(value){
        if (ransomObj[value]) {
            ransomObj[value] += 1
        } else {
            ransomObj[value] = 1
        }
    })
    magazineArr.forEach(function(value){
        if (magazineObj[value]) {
            magazineObj[value] += 1
        } else {
            magazineObj[value] = 1
        }
    })
    
  	// ransomObj에 있는 속성들을 꺼내서 magazineObj에 있는 것들로 전부 쓸 수 있는지 확인하기, 속성이 없거나 적으면 바로 false 반환
    for (const property in ransomObj) {
        if (!magazineObj[property]){
            return false
        } else if (magazineObj[property]<ransomObj[property]) {
            return false
        }
    }
    return true
};

결과 II

I보다 시간과 메모리를 줄였다.
그런데 사실 마음에 드는 결과는 아니다.

기억해야할 것

Object로 iteration 돌리기

const exampleObj = {'a': 12, 'b':23, 'c': 11}
for (const property in exampleObj) {
  console.log(`${property}: ${exampleObj[property]}`)
}
// a: 12
// b: 23
// c: 11