완주하지 못한 선수(js, Lv.1)[해시를 이용한 문제]

 

해시 이해하기.

 

간단한 예제.

// 단어 배열
const words = ["apple", "banana", "apple", "orange", "banana", "apple"];

// 해시테이블 생성
const wordCount = new Map();

// 배열 순회
words.forEach(word => {
    if (wordCount.has(word)) {
        // 단어가 이미 해시테이블에 있으면, 그 카운트를 1 증가
        wordCount.set(word, wordCount.get(word) + 1);
    } else {
        // 단어가 해시테이블에 없으면, 새로운 키로 추가하고 카운트를 1로 설정
        wordCount.set(word, 1);
    }
});

// 결과 출력
console.log(wordCount);

 

has는 값을 탐색. ture / false 값을 return

set은 값을 수정. 원하는(키 : value)값을 새롭게 생성하거나 기존 키의 value값을 수정가능.

---

 

첫 번째 단어 "apple"을 처리한 후:
{'apple': 1}

 

두 번째 단어 "banana"를 처리한 후:
{'apple': 1, 'banana': 1}

세 번째 단어 "apple"을 다시 처리한 후:
{'apple': 2, 'banana': 1}

네 번째 단어 "orange"를 처리한 후:
{'apple': 2, 'banana': 1, 'orange': 1}

다섯 번째 단어 "banana"를 다시 처리한 후:
{'apple': 2, 'banana': 2, 'orange': 1}

마지막 단어 "apple"을 다시 처리한 후:
{'apple': 3, 'banana': 2, 'orange': 1}

---

<문제>

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

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

제한사항

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

입출력 예

participantcompletionreturn

["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
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

---

<제출답안> 시간초과 : 해시를 이용해서 꼭 풀어야 한다.

function solution(participant, completion) {
    
    for(let x of completion){
        let index = participant.indexOf(x) 
         if(index != -1){
             participant.splice(index,1) 
         }
        if(participant.length == 1)break;
     }
    return participant.join("")
    
}

---

아니다... 해시나 내 풀이방법 말고도 풀 수 있는 방식은 많았다.

손쉬운 코드를 한개 가져와봤다. 서로 내림차순 이후에 index를 사용해서 순서가 같지 않은 문자를 가져오는 방식을 취했다.

나의 경우 일일히 같은가 비교해서 제거하는 방식이었으니 이 방법이 훨씬 빠르고 간결하다.

function solution(participant, completion) {
    /*
    for(let i in participant) {
        if(completion.includes(participant[i]) == false) return participant[i];
        completion.splice(completion.indexOf(participant[i]), 1);
    }
    */

    participant.sort();
    completion.sort();

    for(let i in participant) {
        if(participant[i] !== completion[i]) return participant[i];
    }
}