[알고리즘] Hash - 완주하지 못한 선수

JavaScript 스터디를 하면서 자바스크립트 면접 질문을 준비하던 것이 끝나서 이젠 알고리즘을 하루에 한 문제씩 풀기로 했습니다. 그래서 프로그래머스 코딩테스트 연습(https://programmers.co.kr/learn/challenges) 문제를 풀기로 했습니다. 그 중 Hash를 우선적으로 풀고 첫 문제인 '완주하지 못한 선수'(https://programmers.co.kr/learn/courses/30/lessons/42576)를 풀었습니다. 

 

그런데 기묘한 일을 하나 겪은게 있었는데, 정합성 테스트에서 소요 시간이 줄었는데 오히려 효율성 테스트를 통과하지 못한 것입니다. 

 

우선 문제는 이렇습니다.

 

문제 설명

• 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
• 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

 

문제를 처음 풀었던 방식(1번 풀이)은 참가자와 완주자 리스트 모두를 알파벳 순으로 정렬하고, for문을 통해 참가자와 완주자를 비교하여 같지 않으면 반환하는 방식입니다.

const solution=(participant,completion)=>{
  if(participant.length>100000 || participant.length-completion.length !== 1) return;
  let answer;
  let partSort = participant.sort();
  let complSort = completion.sort();
  for(let i=0;i<participant.length;i++){
    if(partSort[i] !== complSort[i]) {
      return partSort[i]
    }
  }
}
solution(["leo", "kiki", "eden"],["eden", "kiki"]); // leo
solution(["mislav", "stanko", "mislav", "ana"],["stanko", "ana", "mislav"]); // mislav
solution(["marina", "josipa", "nikola", "vinko", "filipa"],["josipa", "filipa", "marina", "nikola"]); // vinko

 

1번 풀이의 테스트 결과

그런데 이 풀이는 너무 시간이 많이 걸리는 것 같고, 코드도 너무 긴 것 같아서 개선해보기로 했습니다.

 

개선해 본 풀이(2번 풀이)는 for...of 문을 이용해 각 완주자들의 이름을 뽑아내고, 이 이름을 참가자들과 비교해 같으면 참가자 리스트에서 제거한 후 반복이 끝나면 참가자 리스트에 남은 1명이 미완주자로 이를 반환하는 식이었습니다.

const solution=(participant,completion) => {
  for (let item of completion) {
    if (participant.indexOf(item) !== -1) {
      participant.splice(participant.indexOf(item), 1)
    }
  }
  return participant[0];
}
solution(["leo", "kiki", "eden"],["eden", "kiki"]); // leo
solution(["mislav", "stanko", "mislav", "ana"],["stanko", "ana", "mislav"]); // mislav
solution(["marina", "josipa", "nikola", "vinko", "filipa"],["josipa", "filipa", "marina", "nikola"]); // vinko

 

2번 풀이의 테스트 결과

코드가 짧아지고 속도도 빨라져 개선했다고 생각했는데 막상 테스트를 돌려보니 다른 결과가 나왔습니다. 정확성에선 위 결과에 비해 약 1~4초가량 빨라졌는데, 막상 효율성 테스트에서는 시간 초과로 실패한 것입니다.

 

아직 확실히 어떤 이유인지는 모르겠지만 찾아보고 알게 되면 다시 올리겠습니다.

 

쓰고 나니 또 생각나는 것은 Hash를 이용해서 풀어야 하는 문제 같은데 자바스크립트에서 Hash 역할을 하는 Object나 Map을 하나도 안 써서 그럴 수도 있겠다는 생각이 드는데... 다시 한번 봐야 할 것 같습니다.