1. 문제 설명
- 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수들의 이름을 return 하도록 solution 함수를 작성해주세요.
2. 제한 사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
=> '완주하지 못한 선수는 딱 1명' - 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
=> 배열을 집합으로 보고 차집합을 구하는 방법을 적용할 수 없음
3. 입출력 예
| participant | completion | return |
|---|---|---|
| ["leo", "kiki", "eden"] | ["eden", "kiki"] | "leo" |
=> "leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
| participant | completion | return |
|---|---|---|
| ["marina", "josipa", "nikola", "vinko", "filipa"] | ["josipa", "filipa", "marina", "nikola"] | "vinko" |
=> "vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
| participant | completion | return |
|---|---|---|
| ["mislav", "stanko", "mislav", "ana"] | ["stanko", "ana", "mislav"] | "mislav" |
=> "mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명 밖에 없기 때문에 한 명은 완주하지 못했습니다.
4. 자료구조 & 알고리즘 선택
- 만약 이름 대신 번호가 주어졌다면 선형 배열 이용
- 번호 말고 문자열과 같은 것으로 접근할 수 있는 자료 구조를 선택
1) Hash
- key : 문자열 이름
- hash table : key에 해당하는 value
- hash function : key에 해당하는 value를 저장할 위치 지정
- 다른 key가 같은 칸을 가리키는 collision 발생 가능
=> 또 다른 bucket을 연달아 저장하고 어떤 key의 값인지 적어놓음
2) Dictionary
- 사전의 원소들을 해시를 이용해서 O(1) time에 접근이 가능함
5. 파이썬 문제 풀이
1) 정렬 이용
- 완주하지 못한 선수는 1명이기 때문에 두 배열을 정렬한 뒤 비교를 통해 completion와 같은 인덱스지만 다른 값을 갖는 participant의 값을 반환
def solution(participant, completion):
completion.sort()
participant.sort()
for i in range(len(participant)):
if participant[i] != completion[i]:
return participant[i]
return participant[-1]배열을 정렬하는 연산은 O(NlogN)에 비례하는 복잡도를 가짐
=> 테스트는 통과하지만 문제 크기에 비례하는 선형 시간 알고리즘 X
2) Hash 이용
def solution(participant, completion):
d = {}
for x in participant:
# 사전 d에 x가 처음 저장되는 것이라면 O + 1을 사전에 넣고
# x가 이미 존재한다면 원래 값 + 1을 저장
d[x] = d.get(x, 0) + 1
for x in completion:
d[x] -= 1 # 사전에 있는 값을 1씩 뺌
dnf = [k for k, v in d.items() if v > 0] # key(선수 이름)을 담아냄
answer = dnf[0] # 완주하지 못한 선수의 이름
return answer문제 크기인 N에 비례하는 복잡도를 가짐
line 3-4 : participant 배열 길이에 비례
line 5-6 : 참가자 수인 n에 비례
line 7 : 사전 d의 크기에 비례
=> linear time algorithm
=> hash table을 상수 시간에 읽고 쓸 수 있기 때문에 가능
6. 자바 문제 풀이
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
Map <String, Integer> p = new HashMap<String, Integer>();
int count = 0;
for(int i = 0; i < participant.length; i++){
count = p.getOrDefault(participant[i], 0);
p.put(participant[i], count + 1);
}
for(int j = 0; j < completion.length; j++){
count = p.getOrDefault(completion[j], 0);
if(count > 0){
p.put(completion[j], count - 1);
}
}
for(Map.Entry<String, Integer> entry : p.entrySet()){
if(entry.getValue() > 0){
answer += entry.getKey();
break;
}
}
return answer;
}
}- 자바는
HashMap을 사용해서 해시를 생성할 수 있음 getOrDefault(key, defaultvalue)를 사용하면 파이썬에서get을 사용하는 것과 동일한 결과를 보일 수 있음- 첫 번째 인자로 전달받은 키 값이 해시에 존재하지 않으면 두 번째 인자의 값으로 대신 반환이 됨
put(key, value)을 사용해서 새로운key-value값을 넣거나 기존의key값의value값을 수정할 수 있음entrySet()으로 해시의 모든key-value값을 불러올 수 있음key값을 가져오고 싶다면getKey()value값을 가져오고 싶다면getValue()
Backend development