문제링크: 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"
Solution 1
public String solution(String[] participant, String[] completion) {
Arrays.sort(participant); //이름 순으로 정렬
Arrays.sort(completion); // 이름 순으로 정렬
//참가자와 완주자의 이름을 비교해서 다르면, 완주를 못한 사람이기 때문에 그 값을 return
for(int i=0; i<completion.length; i++){
if(!participant[i].equals(completion[i])){
return participant[i];
}
}
//완주자를 끝까지 비교했는데, 다른 이름이 없다면 참가자의 마지막사람이 미완주자
return participant[participant.length-1];
} 참가자와 완주자의 비교를 위해, 우선 이름 순으로 두 배열 모두 정렬한다. 두 배열의 이름을 비교하여, 이름이 같으면 완주자, 다르면 미완주자로 판단한다. 만약 완주자의 끝까지 비교했을 때, 다른 이름이 없다면, 참가자의 마지막 사람이 미완주자이다.
Solution 2 - Hash 사용
public String solution(String[] participant, String[] completion) {
String answer = "";
//hasp map 생성
HashMap<String, Integer> map = new HashMap<>();
for (String player : participant)
//getOrDefualt : player의 값을 가진 key를 가져와서 없으면 0을 가져와서 1을 더하고,
있으면 그 값을 가져와서 1을 더한다.
map.put(player, map.getOrDefault(player, 0) + 1);
//Hash map에서 완주한 사람 빼기
for (String player : completion)
//기존의 있던 값을 가져와서 -1 한다
map.put(player, map.get(player) - 1);
/*for(string key : map.keySet()){
if(map.get(key) != 0){
answer = key;
break;
}*/
//위의 코드 대신 아래 코드도 사용가능. EntrySet이 반복문을 사용할때 속도가 더 빠름.
Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();
while(iter.hasNext()){
Map.Entry<String, Integer> entry = iter.next();
if (entry.getValue() != 0){
answer = entry.getKey();
break;
}
}
return answer;
}
Hash를 사용해서 문제를 푸는 방법. Hash map을 만들어서 key를 선수이름, value를 선수의 수로 설정한다. completion에서 가져온 선수를 map에서 빼면, 완주를 한 선수는 0이 되고, 완주를 못한 선수는 1로 남아있다. value가 1인 선수가 완주를 못한 선수.
Solution (Python)
def solution(participant, completion):
# 리스트를 이름 순으로 정렬
participant.sort()
completion.sort()
for i in range(len(completion)):
# 순서가 맞지않으면 완주하지 못한 선수
if participant[i] != completion[i]:
return participant[i]
# 위에서 순서가 다 맞았다면 마지막 선수가 완주하지 못한 선수
return participant[-1]
Hello!