[Algorithm] 프로그래머스 완주하지 못한 선수 #해시 #lv.1

최근 프로그래머스에서 진행한 데브매칭에서 코테과제로 알고리즘을 풀어본 후,
뇌가 많이 굳었다고 느껴 알고리즘을 종종 풀어보려고 합니다.

알고리즘은 스스로 풀었을 때의 기쁨이 더 크기때문에,
참조를 위한 포스팅이라기 보다 단순 풀이에 대한 로깅목적으로 적습니다.

문제
출전선수 명단 string[] participant
완주선수 명단 string[] completion
이 제공되었을 때, 완주하지 못한 선수의 이름을 반환하시오.

제약조건

• 출전 선수의 수는 1명 이상 100,000명 이하
• completion의 길이는 participant의 길이보다 1 작음
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있음
• 참가자 중에는 동명이인이 있을 수 있음

처음에는 단순하게 완주자 배열이 1적으니까, 완주자 배열을 순회하면서
각 이름을 출전선수 명단에서 지워나가면 되겠다해서 이렇게 작성했습니다.

function solution(participant, completion){
  // 완주자 이름을 순회하면서,
    completion.forEach(person => {
      // 출전선수 명단에서 이름이 포함되어있으면 삭제한다.
        delete participant.splice(participant.indexOf(person), 1)
    })
    
  // completion의 길이는 participant의 길이보다 1 크므로, 
  // 전체 순회를 하면서 지우면 participant의 길이는 1이되고 완주하지 못한 선수의 이름이 남는다.
    return participant[0]
}

위의 코드는 잘 동작하지만,
결과와 별개로 채점중 효율성측면에서는 통과할 수 없었습니다.

loop가 completion안에서, indexOf(participant)를 사용하기 때문에,
(n-1) * n 시간복잡도 O(n^2)가 나오네요.

복잡도를 계산하는 자세한 방법은 별도로 다른 포스팅을 참고해주세요.

루프를 없애기 위해서 object(javascript)를 사용했습니다.

function solution(participant, completion) {
    const participantInObj = {}
    
    participant.forEach(person => {
        if(participantInObj[person] === undefined){
            participantInObj[person] = 1
        }
        else {
            participantInObj[person] += 1
        }
    })
    
    completion.forEach(person => {
        if(participantInObj[person] === 1){
            delete participantInObj[person]
        }
        else {
            participantInObj[person] -= 1;
        }
    })
    
    
    return Object.keys(participantInObj)[0]
}

위의 코드는 조금 길어졌지만,
object의 키에 직접 접근하는 방식을 이용하여 이중루프를 없애므로써
시간복잡도가 O(n)으로 줄었습니다

이런 방식으로 루프를 사용하는 코드를 대체함으로써 시간복잡도를 줄이고 효율성면에서 점수를 얻을 수 있었습니다.

알고리즘에서 중요한것은 시간복잡도, 공간복잡도가 있습니다. 시간복잡도와 공간복잡도는 다른 포스팅을 참고해주세요. 제가 쉬운것들만 풀어봐서 그런지 몰라도, 아직 공간복잡도까지 신경쓰는 문제는 못봤습니다만, B모 알고리즘 사이트 등에는 메모리 제한 같은 것도 있으므로 관심이 있으면 풀어보시는 것도 좋을 것 같습니다.