완주하지 못한 선수 - 프로그래머스

코딩테스트 연습 - 완주하지 못한 선수

문제 설명

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

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

제한사항

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

---

쉽게 설명하면, 참가자 목록 중에 완주자 목록에 없는 한 명을 찾아내는 문제이다.
비슷한 문제로, 문자열에서 유일하게 2개가 아니고 1개인 문자를 찾아내라는 문제가 있다.
이 비슷한 문제가 내 입사 코딩 테스트에 나왔었던 기억이 난다.

 

내 해결 방법은 이렇다.

1. key-value 자료 구조를 생성한다. 이하 맵(map)이라 부른다.
2. 맵의 key로 참가자의 이름을 넣는다. value는 해당 이름으로 참가한 참가자들의 수다. 즉, 인호가 2명 참가했다면 {'인호': 2} 이런 식이다.
3. 완주자들의 수 만큼 맵의 value를 뺀다.
4. value가 1인 참가자의 이름을 얻는다.

단 한명만 완주하지 못했으므로, value가 1인 참가자의 이름은 오직 한명이며 나머지 value는 0이다.

 

위의 해결 방법을 코드로 해결하기 위한 순서는 다음과 같다.

1. key-value 자료 구조의 객체를 하나 생성한다. 그 객체를 이하의 설명에서 map이라 한다. (이름은 바꿔도 상관 없음) 
2. 모든 참가자들에 대하여 다음의 작업을 실행한다.
   1. 해당 참가자의 이름이 map에 없다면, 새 값을 생성한다. key는 이름, value는 0으로 설정한다
   2. 해당 참가자의 이름을 key로 갖는 value를 1만큼 더한다.
3. 모든 완주자들에 대하여 다음의 작업을 실행한다
   1.  해당 완주자의 이름을 key로 갖는 value를 1만큼 뺀다.
   2. (선택) value가 0이라면 해당 key를 map에서 제거한다.
4. map의 모든 value에 대하여 1인지 확인한 다음, value가 1인 key를 반환한다.

 

위의 순서를 코드로 작성하면 다음과 같다

function solution(participant, completion) {
	// 1. key-value 자료구조 객체 생성
    let map = {};
    
    // 2. 모든 참가자에 대하여
    for (let p of participant) {
    	// 2-1. 참가자의 이름이 key에 없다면 새 값을 추가한다
        if (!!!map[p])
            map[p] = 0
        
        // 2-2. value를 1 더한다.
        map[p]++;
    }
    
    // 3. 모든 완주자에 대하여
    for (let c of completion) {
    	// 3-1. value를 1 뺀다.
        map[c]--;
    }
    
    let answer = '';
    
    // 4. value가 1인 (코드에서는 0 초과인) key를 찾아 반환한다.
    for (let k in map) {
        if (map[k] > 0) {
            answer = k;
            break;
        }
    }
    
    return answer;
}