< 완주하지 못한 선수 문제 > (출처: 프로그래머스)
문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
문제 분석
participant라는 참가자들 중 단 한 선수만 완주하지 못하고 그 선수를 찾아서 return을 하면 됩니다.
completion이 완주자 목록이기 때문에 두 배열을 비교해서 없는 한 명을 찾아내면 됩니다.
이때 동명이인이 있을 수 있다는 것은 데이터 중복이 있을 수 있다는 것이므로 해시 알고리즘을 이용하면 간단하게 해결됩니다.
또는 해시를 이용하지 않고 배열의 정렬을 이용할 수도 있겠습니다.
두 배열을 sort로 정렬시키고 반복문을 통해 두 배열을 같은 인덱스별로 비교했을 때 처음 다른 값이 나온다면 그 값이 완주하지 못한 선수가 되는 거죠.
실제 코드로 작성해 보겠습니다.
문제 풀이
첫 번째 방법 - 해시 알고리즘으로 풀기
function solution(participant, completion) {
const map = new Map();
for(let i = 0; i < participant.length; i++) {
let a = participant[i],
b = completion[i];
map.set(a, (map.get(a) || 0) + 1);
map.set(b, (map.get(b) || 0) - 1);
}
for(let [k, v] of map) {
if(v > 0) return k;
}
}
- 해시 알고리즘을 이용하면 중복 데이터값을 체크하기 편합니다.
- 값을 Map의 키로 잡고 중복 데이터가 나올 경우 값에 +1을 해서 중복 횟수를 파악할 수 있기 때문입니다.
- 완주하지 못한 선수 문제는 중복 횟수가 중요한 것이 아니라 completion에 없는 한 명의 선수를 찾아야 하기 때문에 횟수를 올린 다음 다시 빼는 식으로 코드를 작성합니다. 완주하지 못한 선수는 -1이 안 돼서 1인 상태가 되겠죠.
- 처음 map.set에서 Map에 처음 들어가는 key값이면 (아직 동명이인 선수가 없는 선수 이름) map.get(a)에 값이 없으므로 || 뒤에 있는 0이 되고 +1이 되어 1이라는 값이 들어가게 되고 두 번째 map.set에서 해당 값이 완주하지 못한 선수가 아니라면 값이 있기 때문에 1 값이 들어오고 -1이 되어 해당 선수 키값에는 0이라는 값이 들어가게 됩니다.
- 다음번에 동명이인 선수로 들어가더라도 동일하게 0이라는 값에 +1이 되고 두 번째 map.set에서 다시 -1이 되어 0이 되는 식입니다.
- 그러다가 완주하지 못한 선수인 경우에는 -1이 되지 못해 1이라는 값이 들어가 있게 되고 아래 for문에서 v>0인 조건문에 참이 되어 해당 키 값(선수이름)이 리턴되게 됩니다.
두 번째 방법 - sort후 단순 비교로 찾기
function solution(participant, completion) {
let answer = '';
participant.sort();
completion.sort();
for (let i=0; i<completion.length; i++) {
if (participant[i]!== completion[i]) {
answer = participant[i];
break;
}
}
if (answer === '') answer = participant[participant.length-1];
return answer;
}
- 두 배열을 sort로 정렬하면 값이 한 개 빼고는 다 똑같기 때문에 첫 번째 인덱스부터 비교하면 완주하지 못한 선수가 나오기 전까지는 계속 같은 값이 나오게 됩니다.
- 처음으로 다른 값이 나온다면 해당 값을 리턴하면 됩니다.