Lv.1 - 완주하지 못한 선수 (해시)

안녕하세요. 좋아요요정입니다!

스터디에서 자료구조를 시작했습니다 예~~ 🙌

숙제로 프로그래머스를 시작합니다.

 

---

Lv.1. 완주하지 못한 선수

 

문제 요약

수많은 마라톤 선수들이 마라톤에 참여. 단 한명의 선수를 제외하고는 완주.

마라톤에 참여한 선수들의 이름이 담긴 배열과 완주한 선수들의 배열이 주어졌을 때 완주하지 못한 단 한명의 선수를 반환하는 함수를 작성.

 

 

제한 사항

• 마라톤 경기에 참여한 선수의 수는 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차 시도

전략 완주하지 못한 사람은 무조건 1명이고, 동명이인에 고유값이 있지 않기 떄문에 동명이인의 순서는 상관이 없다. 참가자 명단을 순회하며 완주자를 하나씩 제거해주다가 없는 경우 그 값을 리턴해줘보자!

 

- completion 배열의 복제 배열을 만든다.

- participant의 배열에 filter로 순회를 돌린다.

- person을 복제된 배열.indexOf로 찾은 뒤 없다면 반환, 있다면 해당 항목은 확인 완료! 복제된 배열에서 제거해준다.

//1차시도
function solution(participant, completion) {
    var answer = '';
    const completionList = [...completion];
    answer = participant.filter(person => {
    	let index = completionList.indexOf(person);
        if(index == -1) {
        	return person;
        } else {
        	completionList.splice(index, 1);
        }
    })
	return answer[0];
}

 

 

실행 결과

문제점

1. [...] 로 배열을 복사하면서 1번 순회

2. filter로 순회 중 내부에서 삭제하는 splice메소드로 2중 순회가 됨 (기하 급수적..~!)

O(n) + O(n^2) 의 순회가 이루어졌다.. 하핫

 

 

 

 

 

2차 시도

전략 두 배열을 보두 정렬한 뒤 나란히 두고 비교해보면,  '다른'곳이 완주하지 못한 1명이 포함되어있는 곳이다. 

 

- 두 배열을 sort()해줌.

- index를 +1씩 올려주며 두 배열을 비교해주고  같이 않은 경우 반복을 멈춤! 그 index가 바로 완주하지 못한 사람이다.

//2차시도
function solution(participant, completion) {
   var answer = '';
   participant.sort()
   completion.sort()
   let index = 0
   while (participant[index] == completion[index]) {
        index ++;
    }
    return participant[index];
}

 

실행 결과

뿌듯하게(?) 성공했습니다..

 

 

끝이 아닙니다. 그리고 대망의 스터디날

스터디를 진행하는 hoon님이 sort를 이용하셔서 '와 신난다! 맞았다!' 했는데 시원하게 리팩토링해버리시네요~!

 

2차 시도의 문제점

- 두번의 sort 메소드와 1번의 루프를 이용. 

자바스크립트가 사용하는 sort는 merge sort기술을 활용하기 때문에 O(n log n)의 속도로 실행된다. 따라서 크게 느리지는 않지만, O( 2n log n + n )의 시간 복잡도를 갖는다. 

 

sort...!! 세상에 sort 역시 데이터를 정렬하며 반복될 것이라는 것을 생각하지 못했습니다.. ㅎㅎ

 

 

 

 

러버덕 스터디 피드백(by hoon) 

- 자바스크립트 객체를 만든다

- 완주한 사람의 이름을 해당 객체의 키로, 값은 몇 명이 있는지 체크해준다

- 참가한 사람의 이름으로 루프를 돌린다

- 완주한 사람 이름으로 만든 객체에, 참가한 사람의 이름을 제거한다

- 만약 객체에 참가한 사람의 이름이 없다면, 반환한다

const solution = (participants, completed) => {
  const completedRunners = {};

  let unFinishedRunner = '';

  completed.forEach((runner) => {
    completedRunners[runner] = completedRunners[runner] + 1 || 1;
  });

  participants.forEach((runner) => {
    if (completedRunners[runner]) {
      completedRunners[runner] = completedRunners[runner] - 1;
    } else {
      unFinishedRunner = runner;
    }
  });

  return unFinishedRunner;
}

 

실행 결과

크으 속도가.. 반 넘게 줄었습니다!! 👍🎉🎉🎉 크으~~~!!!! 

너무 재밌고 신기하네요!!  

 

 

 

 

어...?🤔

2차시도에서 사용했던 완주하지 못한 사람을 찾을 경우.. while문으로 반복문을 빠져나가게 짠다면? 

const solution = (participants, completed) => {
  const completedRunners = {};
  completed.forEach((runner) => {
    completedRunners[runner] = completedRunners[runner] + 1 || 1;
  });
    let index = 0
   while (completedRunners[`${participants[index]}`]) {
      completedRunners[`${participants[index]}`] = completedRunners[`${participants[index]}`] - 1;
        index ++;
    }

  return participants[index];
}

데이터가 클 때 좀 더 빨리 끝낼 수 있을 것 같습니다 오오.. 너무 신기하네요

 

 

 

 

 

Map을 사용한다면..??

const solution = (participants, completed) => {
  const completedRunners = new Map();

  let unFinishedRunner = '';

  completed.forEach((runner) => {
      completedRunners.set(runner, completedRunners.get(runner) + 1 || 1)
  });
    let index = 0
   while (completedRunners.has(participants[index])) {
     completedRunners.set(participants[index], completedRunners.get(participants[index]) - 1)
       if(completedRunners.get(participants[index]) === 0) {
           completedRunners.delete(participants[index])
       }
        index ++;
    }

  return participants[index];
}

  더 빠를까? 생각했는데 결과는 비슷하네요 오우.. 신기합니다

 

프로그래머스.. 처음 풀어봤는데 너무 재미있어요!

 "해시"라는 카테고리로  key-value쌍으로 데이터를 빠르게 찾아보라는 힌트가 있었네요

다음부터는 내가 얻을 수 있는 정보를 제대로 파악할 수 있도록 꼼꼼하게 문제를 살펴봐야겠습니다 :)!! 

 

행복한 코딩라이프되세요~~!