[JS|해시] 프로그래머스 42576번. 완주하지 못한 선수

 

프로그래머스

 

---

1. 입력과 출력

• 입력
  • 마라톤에 참여한 선수들의 이름이 담긴 배열 participant ( 1 ≤ n ≤ 100,000 )
  • 완주한 선수들의 이름이 담긴 배열 completion ( n -1 )
• 출력
  • 완주하지 못한 선수의 이름 return

 

2. 문제 풀이 로직

문제 풀이 로직 설명

 

• 마라톤에 참여한 선수들의 이름들이 담긴 배열 participant에서 완주하지 않은 선수의 이름을 출력해야 한다.

 

 

• 참여 선수 명단 participant 배열을 해시테이블 형태로 바꾼다.
  • 해시테이블은 JS의 Object 형태로 만든다. 
    • Key(키) : 선수 이름
    • Value(값) : 해당 선수 이름의 갯수

 

 

• 완주 선수 명단 completion 배열을 돌면서 해시테이블 내 선수 이름의 갯수를 하나씩 줄인다.

 

 

• 완주한 모든 선수를 대상으로 갯수를 하나씩 줄이고 난 뒤
• 해시테이블에 남아있는 이름의 갯수가 1개인 선수는 완주를 하지 못한 선수이므로 해당 선수 이름을 반환한다.

 

 

풀이 시간 및 시간 복잡도 설명

• 총 30분 풀이
• 시간복잡도 : O(N)
  • 참여 선수 목록(N)을 돌며 hashTable에 저장함 -> O(N)
  • 완주 선수 목록(N-1)을 돌며 참가자 갯수를 -1씩 줄임 -> O(N-1) 

 

 

3. 전체 코드

function solution(participant, completion) {
  let hashTable = new Object()

  // 1. 참가자 목록을 돌며 hashTable에 { 참가자이름(Key): 동명이인 포함 사람 수(Value) } 형태로 저장
  participant.map((player) => {
    // hashTable[player] ? hashTable[player] : 0
    //  ㄴ 만약 이미 동명이인이 hashTable에 저장되어있다면 해당 값을 꺼내와서 +1
    //  ㄴ 그렇지 않다면, 1로 초기화
    hashTable[player] = hashTable[player] ? ++hashTable[player] : 1
  })

  // 2. 완주한 참가자 목록을 돌며 hashTable에 저장되어있는 사람 수(Value)를 -1
  completion.map((player) => hashTable[player]--)

  // 3. hashTable에 사람 수가 남아있는 이름은 완주하지 못한 이름이므로 그대로 반환함
  for (const player in hashTable) {
    if (hashTable[player] === 1) return player
  }
}