프로그래머스에 위클리 문제가 없어져서, 코딩 테스트 고득점 Kit의 문제를 풀어보기로 했다. 그 중 가장 처음에 있는 해시 부터 시작!

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

participant	completion	return
[“leo”, “kiki”, “eden”]	[“eden”, “kiki”]	“leo”
[“marina”, “josipa”, “nikola”, “vinko”, “filipa”]	[“josipa”, “filipa”, “marina”, “nikola”]	“vinko”
[“mislav”, “stanko”, “mislav”, “ana”]	[“stanko”, “ana”, “mislav”]	“mislav”

나의 풀이

처음에는 참가자 배열과 완주자 배열의 선수 이름을 하나씩 비교했다. 그리고 같은 이름이 있다면 참가자 배열에서 삭제해주었다.

중복된 이름이 존재할 수 있기때문에 차집합으로 찾지 않았고 하나씩 비교하는 것을 선택했는데, 이렇게 하니 테스트1~3은 통과했지만 for문에 map까지 돌려서 시간초과가 되었다. 같은 이름을 찾기까지 배열을 모두 돌아야할 수도 있기 때문이다. 지금봐도 효율성이 떨어저 보인다. 😭

function solution(participant, completion) {
  let length = participant.length;
        
  for(let i = 0;  i<length; i++){
    participant.map((person, idx)=>{ 
      if(person.includes(completion[i])) {
        return  participant.splice(idx,1)
        }
      })
    }
  return participant[0]
}

이번에는 선수의 이름 비교를 위해 배열을 끝까지 돌지 않도록 먼저 참가자,완주명단을 sort()로 정렬해주었다. 정렬 후 선수 이름을 비교하면 배열의 값 하나당 한번만 비교하면되고, 선수이름이 다르다면 그 선수가 완주하지 못한 선수이므로 return 해주면된다. 👍🏻

function solution(participant, completion) {
    participant.sort();
    completion.sort();

      for (let i = 0; i < participant.length; i++){
        if(participant[i] !== completion[i]){
          return participant[i]
        } 
      }
  }

다른 분 풀이

Map()의 속성을 이용해 풀으셨다. 이 풀이를 하나하나 뜯어보면서 진짜 많이 배웠다…👍🏻

새로 생성한 map안에 participant.length만큼 key-value값을 set한 뒤,
participant[i]와 completion[i]을 고유한 key값으로, map.get(key)은 value값으로 사용했다.
participant[i]와 completion[i]을 set하면서 map.get(key)같은 데이터를 덮어씌우는 특성을 이용해 value값을 +-했다.
completion한 선수는 value값으로 0을 갖게되고, completion하지 못한 선수는 value값으로 1을 갖게된다.
map을 for-of문으로 순회시켜 value값이 0보다 큰 값을 리턴했다.

function solution(participant, completion) {
    const map = new Map();


    for(let i = 0; i < participant.length; i++) {
        let a = participant[i], 
            b = completion[i];

        map.set(a, (map.get(a) || 0) + 1); // 중복되는 이름은 +1씩 늘어남
        map.set(b, (map.get(b) || 0) - 1); // participant와completion 명단 모두에 이름이 있으면 -1됨. 
    }

    for(let [k, v] of map) {
        if(v > 0) return k;
    }

    return 'nothing';
}