[프로그래머스][JS] 완주하지 못한 선수

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

프로그래머스

풀이 과정

function solution(participant, completion) {
    // participant.sort()
    // completion.sort()
    var answer = '';
    let obj1 = {}
    let obj2 = {}
    for (let i = 0; i < participant.length; i++){
        if (obj1[participant[i]]){
            obj1[participant[i]]++
        }else{
            obj1[participant[i]] = 1
        }
    }
    for (let i = 0; i < completion.length; i++){
        if (obj2[completion[i]]){
            obj2[completion[i]]++
        }else{
            obj2[completion[i]] = 1
        }
    }
    // console.log(obj1, obj2)
    let total = []
    for (const [key, value] of Object.entries(obj1)){
        // console.log(key, value)
        if (obj1[key] !== obj2[key]){
            total.push(key)
        }
    }
    // console.log(total.join(''))
    return total.join('');
}

이 문제는 해시 알고리즘을 이용하여 푸는 문제이다.

해시 알고리즘은 (해시맵) 객체를 사용하는데, 키-값 쌍의 데이터를 저장하고 검색하는 데 사용되며, 객체나 맵과 유사한 역할을 한다.

 

각 매개 변수를 객체로 만든 후 비교를 하면된다.

Object.entries() 메서드로 반복문을 사용하여 두 객체를 비교하는데 두 value가 다른 경우에 해당 key를 total 빈 배열에 push 하면 원하는 값을 얻을 수 있다

total은 배열이고 문제에서 원하는 타입은 문자열이기 때문에 마지막에 join메서드를 사용하여 형변환을 한 후 반환한다.

---

리뷰

처음에 해시 알고리즘이 뭔지 몰라서 이중 반복문을 사용하여 완전탐색으로 풀었더니 시간 초과가 발생해서

해시 알고리즘이 객체를 이용한 알고리즘인 걸 알고 나서 객체로 시도를 했더니 통과를 했다

코드 초반에 정렬을 했었는데 정렬을 하면 시간초과가 발생한다. sort메서드의 시간복잡도가 O(n log n)인데 해시맵을 사용했기 때문에 배열을 정렬하여 시간을 낭비할 이유가 없다.