고득점 키트 - 해시1(프로그래머즈)

anonymous·2021년 5월 12일

알고리즘

목록 보기

10/12

🏃‍♂️ 완주하지 못한 선수

문제 설명

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

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

제한사항

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

문제 해석

1 argument : participants 배열
2 argument : completion 배열

3 method : 완주하지 못한 선수의 이름 (동명이인도 있음) 을 추출

select element from participant and search for element in completion array
if found remove from completion array
if not found add to return array

ex)
partipant
leo, kiki, eden

completion
eden, kiki

return
leo

//Solving Steps
/*
1 Interpret the problem (until it's intuitively understood)
 : argument
 : steps
 : return
 : data types used
2 Create concrete example (simple and easy example)
3 List tools that I could/might use and write psudocode
4 Try different approaches to Solve
5 Refactor, Recap

- 3 arrays- participant, completion, incomplete
- loop, if-else, 
*/

//BASE
function solution(participant, completion) {
    for(i in participant)
    
    var answer = '';
    return answer;
}

//METHOD 1
function solution(participant, completion) { 
    const obj = {}
    for (let p of participant) {
        obj[p] = obj[p] ? obj[p] + 1 : 1
    }
    for (let c of completion) {
        obj[c] -= 1
    }
    for (let key in obj) {
        if (obj[key] == 1) {
            return key
        }
    }
}

let participant = ["leo", "kiki", "eden"];
let completion =  ["eden", "kiki"];

console.log(solution(participant, completion));

//METHOD 2 
function solution(participant, completion) {
        participant.sort();
        completion.sort();
        for(let i in participant){
            if(participant[i] !== completion[i])
                return participant[i];
        }
    }

//METHOD 3
const solution = (p, c) => {
    p.sort()
    c.sort()
    while (p.length) {
        let pp = p.pop()
        if (pp !== c.pop()) return pp
    }
}

//METHOD 4
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;
    });
}

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

    for(let i = 0; i < participant.length; i++) {
        let a = participant[i], 
            b = completion[i];
        //set participant value to key
        //set count by checking if participant value exists  
        map.set(a, (map.get(a) || 0) + 1);
        //if map of b exist - 1 to value if not 0 
        map.set(b, (map.get(b) || 0) - 1);
    }

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

    return 'nothing';
}

//METHOD 6
/*
// array, map, loop (for, forEach), conditional 사용
1 participant 요소를 key 값에 추가하고 발생 횟수를 value 값에 추가.
2 completion 요소를 이전에 key값에 추가한 map에서 확인해서 있으면 횟수 빼기. 
3 키 값을 순회해서 value 횟수가 있으면 키 값 리턴
*/
function solution(participant, completion) {
    const hash = {};
    //1 participant 요소를 key 값에 추가하고 발생 횟수를 value 값에 추가. 
    for(let val of participant) {
      if(!hash[val]) hash[val] = 0;
      hash[val]++;
    }
    //2 completion 요소를 이전에 key값에 추가한 map에서 확인해서 있으면 횟수 빼기. 
    const result = completion.forEach(val => hash[val]--);
    //3 키 값을 순회해서 value 횟수가 있으면 키 값 리턴
    for(let key in hash) if(hash[key]) return key;
}

Map 객체는 키-값 쌍을 저장하며 각 쌍의 삽입 순서도 기억하는 콜렉션입니다.

입출력 예

입출력 예 설명
예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

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

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

Map 사용 예제

let myMap = new Map()

let keyString = '문자열'
let keyObj    = {}
let keyFunc   = function() {}

// 값 설정
myMap.set(keyString, "'문자열'과 관련된 값")
myMap.set(keyObj, 'keyObj와 관련된 값')
myMap.set(keyFunc, 'keyFunc와 관련된 값')

myMap.size              // 3

// getting the values
myMap.get(keyString)    // "'문자열'과 관련된 값"
myMap.get(keyObj)       // "keyObj와 관련된 값"
myMap.get(keyFunc)      // "keyFunc와 관련된 값"

myMap.get('문자열')    // "'문자열'과 관련된 값"
                         // keyString === '문자열'이기 때문
myMap.get({})            // undefined, keyObj !== {}
myMap.get(function() {}) // undefined, keyFunc !== function () {}