[programmers] 해시 - 완주하지 못한 선수

https://programmers.co.kr/learn/courses/30/lessons/42576

문제

[문제 설명]

 

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

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

 

[제한사항]

• 마라톤 경기에 참여한 선수의 수는 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
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

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

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

참여자 명단 배열과 완주자 명단 배열을 비교를 할 것입니다. 배열을 비교할 때 이중 for문을 사용하게 되면 시간복잡도에 걸리게 됩니다.

그렇기 때문에 배열을 정렬한 후에 배열을 비교해 한 개의 for 문으로 배열을 비교해보겠습니다.

 

다음은 예시를 정렬한 후의 값입니다.

 

예 #1

[ 'eden', 'kiki', 'leo' ]
[ 'eden', 'kiki' ]

예 #3

[ 'ana', 'mislav', 'mislav', 'stanko' ]
[ 'ana', 'mislav', 'stanko' ]

 

1번 예시대로 차이값이 마지막에 나오는 경우 for 문이 끝나고 난 다음에 참여자 마지막 값을 반환해줍니다.

3번 예시대로 차이값이 중간에 나오는 경우는 순서대로 비교를 해서 값이 다를 경우 다른 번째의 참여자를 반환해줍니다.

해결코드 [javascript]

function solution(participant, completion) {
    var answer = '';
    
    // 참여자 명단과 완주자 명단 정렬
    participant.sort();
    completion.sort();
    
    // 참여자 명단과 완주자 명단 순서대로 비교
    for(var i =0; i<completion.length; i++){
        // 참여자 값과 완주자 값이 다를 경우
        if(participant[i] != completion[i]){
            // 참여자 값 반환
            answer = participant[i]
            return answer;
        }
    }
    
    // 차이값이 마지막에 있을 경우 참여자의 마지막 값을 반환
    answer = participant[completion.length]
    return answer;
}

 

사용한 알고리즘/함수

사용한 함수 : sort()
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Array.prototype.sort()

Epilogue

해시 카테고리에 있기 때문에 key-value 쌍으로 데이터를 저장하는 자료구조를 한 번 더 생각해 보았습니다.

key:참여자이름 value:0(참여만 했을 경우 0, 참여도 하고 완주도 했을 경우 1)

예 #1

[ 'eden', 'kiki', 'leo' ] 
[ 'eden', 'kiki' ]

참여자 배열을 순회하면서 다음과 같은 object 를 만들고 난 뒤,

{

   "eden" : 0,

   "kiki" : 0,

   "leo" : 0

}

완주자 배열을 순회하면서 value 값을 1로 변환해줍니다.

{

   "eden" : 1,

   "kiki" : 1,

   "leo" : 0

}

완성된 object 에서 해당 키가 없거나, 저장된 값이 0 이면 그 참가자를 반환하는 방법도 있습니다.