[JS / 알고리즘] 완주하지 못한 선수

sunaaa·2021년 9월 2일
0

알고리즘

목록 보기
3/3

완주하지 못한 선수

정렬

  • hash로 푸는 폴더에 있던 문제였는데 일단 정렬로 풀었다.
function solution(participant, completion) {
  // 참여자를 순서대로 정렬한다
   participant.sort();
  // 완주자를 순서대로 정렬한다
   completion.sort();
  // 참여자의 수만큼 순회를 돈다. 정렬된 참여자와 완주자 배열에서 같은 인덱스 값에 다른 값이 들어있으면 참여자 배열의 해당 인자를 return해준다.
   for( let i = 0; i<participant.length; i++) {
     if(participant[i] !== completion[i]) {
        return participant[i]
     }
   }
}

해시

  • 간단하게는 임의의 key-value를 만들어 푸는 방법이라고 이해했다

개념

  • 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것
  • 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array 이다
  • 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이때 사용하는 함수(알고리즘)를 해시함수 라고 한다
  • 해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 매우 빠르다

방법1

function solution(participant, completion) {
    const hash = {};
  // 참여자 배열의 원소를 key로 받고 배열에서 각 원소의 중복 개수를 세는 것을 value로 받는 hash를 만든다.
  // 해시에 아직 해당 참여자 key값이 없으면 참여자 key값을 만들어준다.
  // 참여자 각 요소를 순회하며 key값이 나올때마다 value값에 1씩 더해준다
    for(let val of participant) {
      if(!hash[val]) hash[val] = 0;
      hash[val]++;
    }

  // 완주자 배열을 순회하며 hash에 각 완주자key의 value값에 -1씩 감소시켜준다.
    completion.forEach(val => hash[val]--);
// hash에 있는 value 중에 0이 아닌 값이 있다면 그 값의 key를 결과로 리턴해준다.
    for(let key in hash) if(hash[key]) return key;
}

방법2

  • 다른 사람의 풀이 참고
  • reduce랑 find 메소드를 자유롭게 쓰면 깔끔하게 풀 수 있다.
function solution(participant, completion) {
  // dic이라는 key-value 객체를 만들어준다
  // 누적값은 obj, 각 요소는 member로 받는다
  // 지금까지 누적된 obj에 member 키값이 있으면 value에 1을 더하고, 아니면 value에 1을 할당해준다.
  // 누적값인 obj가 리턴된다.
  const dic = completion.reduce((obj, member) => ( obj[member] = obj[member] ? obj[member]+1 : 1
, obj), {})
  
  // 참가자를 dic에서 찾는다. 값이 있으면 dic의 value에서 1을 빼준다.(= 남은 완주자 명단에서 체크하면 -1을 시켜주는 것.)
  // 완주자 명단에 없거나 남은 카운트가 0이면 그 값을 뽑아내고 리턴해준다(find는 조건을 콜백함수로 받아 해당 조건을 충족하는 첫번째 값 하나를 리턴해주는 메소드다.)
  return participant.find(val => 
    dic[val] ? dic[val] = dic[val]-1 : true
  )
}
profile
Be Playful Front-end Developer

1개의 댓글

comment-user-thumbnail
2021년 11월 24일

안녕하세요 ! ORM검색으로 들어오게 되었는데 글이 정말 잘 설명되어있어서 큰 도움 받았답니다. 감사해요. 혹시 독학중이신가요?

답글 달기