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

24년 12월 28일
해결한 문제 갯수: 4

 

문제 설명

 

 

문제 분석

• 마라톤에 참여한 선수들의 명단(participant)과 완주한 선수들의 명단(completion)이 주어집니다.
• 단 한 명의 선수를 제외하고는 모든 선수가 완주했습니다.
• 완주하지 못한 선수의 이름을 찾아야 합니다.

 

첫 번째 접근:  Array.splice() 사용 (시간 초과)

function solution(participant, completion) {
    return completion.reduce((a, c) => {
        const idx = participant.indexOf(c)
        a.splice(idx, 1)
        return a
    }, participant)[0]
}

indexOf()와 splice() 메서드는 각각 O(n) 시간 복잡도를 가지므로, 전체적으로 O(n²) 시간 복잡도를 가집니다. 역시 큰 데이터셋에서 비효율적입니다.

 

두 번째 접근: 정렬 후 비교 (시간 초과)

function solution(participant, completion) {
    participant = participant.sort((a, b) => a.localeCompare(b))
    completion = completion.sort((a, b) => a.localeCompare(b))
    
    return participant.filter((el, i) => el !== completion[i])[0]
}

각 배열의 요소를 정렬한 후 participant와 competion의 동일 인덱스에서 서로 다른 요소를 필터링 합니다. 이후 첫번째 요소를 반환합니다.

 

세 번째 접근: 해시 테이블 사용

function solution(participant, completion) {
    let obj = participant.reduce((a, c) => {
        if(a[c]) a[c] += 1
        else a[c] = 1
        return a
    }, {})
    
    completion.forEach(el => {
        obj[el] -= 1
    })
    
    return Object.entries(obj).filter(([_, v]) => v)[0][0]
}

개선 사항

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)
• 각 선수의 등장 횟수를 카운팅하여 한 번의 순회로 문제를 해결합니다.