[Programmers Level 1 해시] 완주하지 못한 선수 Javascript

⚡문제정보

 

 

한명 빼고 모두 완주한 마라톤 경기에서

완주를 못한 찐따 한명을 찾는 문제입니다.

동명이인이 있다는 조건이 있으니 단순하게 filter()를 이용해서 푸는 방법은 제한이 있을 것 같아요

항상 한명빼고 완주를 못하니까 두 배열을 비교해서 completion 배열에는 없는 한명을 찾아내면

되는 문제라고 생각했습니다.

---

 

🙄제한사항

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

 

 

---

 

 

🔍접근방법

 

없는 한명을 찾으면서 동명이인 케이스를 제거하기 위해 객체를 선언해주고

completion배열을 객체에 동명이인까지 고려해서 담아준 다음

participant와 비교해주면서 완주하지 못한 사람을 찾으려고했습니다. 

 

---

 

 

🔍나의 풀이

 

function solution(participant, completion) {
    
    function findrunner(part) {
        let runner = new Object()
        for(i=0; i< part.length ; i++) {
            if(runner[part[i]] == undefined) {
                runner[part[i]] = 1
            } 
            else if (runner[part[i]] != undefined){
                runner[part[i]]++
            }
        }
        return runner
    }
    
    let problem = findrunner(participant)
    
    for(i=0 ; i<completion.length ; i++) {
        problem[completion[i]]--
    }
    return Object.entries(problem).sort((a,b) => b[1] - a[1])[0][0]
}

 

통과는 했습니다만

다른 사람들의 풀이를 보니 효율적으로 풀지 못했다는 생각이 들었습니다.

sort()를 사용하지않고도 풀 수 있을텐데라는 생각도 들고

Map을 사용해서 풀걸하는 생각이 드네요

 

코드 해석은 다음과 같습니다.

 

function solution(participant, completion) {

	//participant를 객체로 바꿔줄 함수를 만들기
    function findrunner(part) {
        let runner = new Object()
        for(i=0; i< part.length ; i++) {
            if(runner[part[i]] == undefined) {
                runner[part[i]] = 1
            } 
            //만약 처음 만나는 키라면 1을 할당해줌
            else if (runner[part[i]] != undefined){
                runner[part[i]]++
            }
            //중복키라면 ++, if()는 생략해도 무방함
        }
        return runner
    }

    let problem = findrunner(participant)
    // 함수에 participant를 넣은 결과를 담은 변수 선언

    for(i=0 ; i<completion.length ; i++) {
        problem[completion[i]]--
        //completion의 모든 키를 순회하면서 빼주면 value값이 1인 값 한개와
        //value가 0으로 구성된 나머지 값들이 만들어짐
    }
    return Object.entries(problem).sort((a,b) => b[1] - a[1])[0][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);
        map.set(b, (map.get(b) || 0) - 1);
    }

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

    return 'nothing';
}

 

Map 자료구조를 이용한 풀이입니다.

set을 이용하면 map에 키와 값을 할당시켜줄 수 있는데

만약 a가 값이 있다면 ++ 해주고 값이 없다면 or연산자로 0을 넣어준다음 +1을 해주는 식인가보네요

 

Map을 열심히 공부해놓고 익숙하지않다고 안 쓴 과거를 반성합니다

 

function solution(participant, completion) {
    var dic = completion.reduce((obj, t)=> (obj[t]= obj[t] ? obj[t]+1 : 1 , obj) ,{});
    return participant.find(t=> {
        if(dic[t])
            dic[t] = dic[t]-1;
        else 
            return true;
    });
}

 

reduce와 find를 이용한 풀이입니다.

잘 이해가 안가는데 obj[t] ?만 해도 어떻게 저 삼항연산자가 돌아가는지..?

---

🔍쪼끔 더 개선한 나의 풀이

function solution(participant, completion) {
  let map = new Map()
  for(i=0 ; i<participant.length; i++) {
      map.set(participant[i], map.get(participant[i])  + 1 || 0 +1 )
      /* 맵자료구조는 .set() 을 통해 키밸류 값을 집어넣을 수 있음
      set(키, 밸류)을 설정하는 형태
      get은 맵자료구조.get(키) 의 형태로 사용하고 return값은 키의 밸류값임
      
      다만 맵자료구조에서 정의되지않은 키값의 밸류는 항상 undefined임
      따라서 위의 경우 || 단축평가를 통해 앞의 값이 falsy값(undefined,null,0,false 등등)이면 뒤의 값을 반환하게해서
      한번도 등장한적 없는 키라면 밸류를 0+1해주고
      등장한적있는 키라면 get(키) +1을 해주는 식으로 코드를 짰음
      읽기 쉽게 하기위해 0 + 1을 해줬지만 그냥 value를 1로 지정해도 무방함

      만약 위 코드를 if문 형태로 구현한다면 다음과 같을것임

      if(map.get(participant[i]) != undefined) {
        map.set(participant[i], map.get(participant) +1)
      }
      else {
        map.set(participant[i] , 1)
      }

      */
  }
  for(i=0 ; i<completion.length; i++) {
      map.set(completion[i], map.get(completion[i]) - 1)
      /* 위코드와 마찬가지로 set과 get을 사용해서
      밸류값을 -해줌 이 과정을 끝까지 반복하면 밸류가 1인 키가 단 하나 존재하게될것임 
      */
  }
  return [...map].filter(ele => ele[1] != 0)[0][0]
  /* map 자료구조를 전개연산자를 이용해 map 자료구조를 2차원 배열 형태로 바꿔준뒤
  배열 메서드 filter를 통해 밸류값이 0인 경우를 모두 지워줌
  그결과 filter까지 거친 경우 값은
  [[키값,1]]의 형태가 될것임 우리가 원하는 리턴값은 완주하지못한선수의 이름이니까
  [0][0]을 통해 키값에 접근해서 리턴해줌
  */
    
}