https://school.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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
참여자 배열로 "참여자이름": 참여자수 로 된 Map을 만들어줬다.
입출력 예제 #1을 예시로 든다면
{"leo":1}, {"kiki":1}, {"eden":1} 이런 형식의 Map
완주자 배열을 순회하며, Map에 해당 참여자 이름이 있을때 참여자수를 -1 해줬다.
{"leo":1}, {"kiki":0}, {"eden":0}
순회가 끝난뒤 참여자 Map을 확인해보면 완주자들은 value가 0일것이고, 완주를 하지 못했다면 1일 것이다.(만약 동명이인이 있을경우는 1이상)
마지막으로 Map을 순회하며 value가 0보다 큰 key값(이름)을 리턴해준다.
function solution(participant, completion) {
const map = new Map();
for(let p of participant){
if(map.has(p)){
map.set(p, map.get(p)+1);
} else {
map.set(p, 1);
}
}
for(c of completion){
if(map.has(c)){
map.set(c, map.get(c)-1);
}
}
for(let [p, num] of map){
if(num>0) return p;
}
}
N: participant 배열의 길이(1 이상, 100,000이하) 라고 가정
O(N)
처음 반복문에서 participant 배열을 순회하며 map을 만들어줌.(N)
두번째 반복문에서는 completion 배열을 순회하며 map의 값을 변경시켜 줌.(N-1, completion 배열 길이는 participant 배열길이보다 항상 1만큼 작기때문에)
마지막으로 map의 값을 순회하며 value가 0보다 큰 key값을 리턴해줌. 이때 map의 [key, value] 쌍은 항상 N보다 작거나 같을것. (대략 N)
=> O(3N-1) => O(N)
O(N)
새로 생성하는 map의 [key, value] 쌍은 항상 N보다 작거나 같을것. (대략 N)
참가자 배열과 완주자 배열을 정렬해준다.
그리고 두 배열을 인덱스 0 부터 비교하면, 참가자 배열에 완주하지 못한 선수가 나올때 참가자배열의 원소와 완주자배열의 원소가 달라질 것이다. 그때 참가자 배열에 있는 완주하지 못한 선수의 이름을 리턴해준다.
function solution(participant, completion) {
const p = participant.sort();
const c = completion.sort();
for(let i=0; i<participant.length; i++){
if(p[i]!==c[i]) return p[i];
}
}
N: participant 배열의 길이(1 이상, 100,000이하) 라고 가정
O(NlogN+N)
정렬할때 NlogN * 2
for문 순회할때 N
O(N)
정렬된 배열 p,c가 새로 생성될때 2N 만큼 필요.
=> O(2N) => O(N)