[알고리즘] 완주하지 못한 선수

---

문제 파악

완주하지 못한 선수

마라톤 선수들이 마라톤에 참여했다.

단 한 명을 제외하고는 모두 완주했다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant과, 완주한 선수들의 이름이 담긴 배열 completion이 주어진다.

완주하지 못한 선수의 이름을 return하라.

입력

participant	completion
["leo", "kiki", "eden"]	["eden", "kiki"]
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]

출력

return
"leo”
"vinko”
"mislav”

---

접근 방법

배열의 정렬을 이용한 풀이(현재 풀이)

문자열도 정렬을 할 수 있을까? → 문자열도 Arrays.sort를 이용해서 정렬이 가능하다.

문자열 정렬을 확인했으니 이 문제는 간단하게 풀 수 있을 것 같다.

주어진 입력은 규칙이 있다.

참가자와 완주자에는 단 한 명의 이름이 없다는 것 외에는 동일하다.

그럼 두 배열을 오름차순으로 정렬시킨 후 서로 비교해서 없는 사람을 찾으면 된다.

하지만 여기엔 반례가 있다.

두 배열에는 길이가 1만큼 차이가 있으며, 완주하지 못한 사람이 가장 마지막에 있을 경우가 그 예이다.

그에 대해선 if로 조건을 처리해주면 될 것이다.

문제 알고리즘 구현 순서

1. 두 배열을 정렬한다.
   • 정렬이 되면 두 배열은 같은 순서와 같은 값을 가질 것이다.
   • 참가자와 완주자 명단은 한 명의 유무를 제외하고는 동일하기 때문이다.
2. for 반복문을 하나 생성하고 두 배열을 비교한다.
   • 완주한 선수 배열이 길이가 더 짧으니 완주한 선수 배열의 길이로 반복 횟수를 설정한다.
   • 순서를 정렬했으니, 순차적으로 비교해도 값은 일치할 것이다.
   • 중간에 일치하지 않는 경우가 바로 완주하지 못한 선수의 이름이다.
   • 만약 일치하지 않는 경우를 찾지 못 하고 반복문이 끝난다면, 참여 선수 배열의 마지막 값이 완주하지 못한 선수의 이름이 된다.

시간 복잡도: O(n log n) → 정렬의 시간 복잡도이다.

---

HashMap을 이용한 풀이(찾아본 다른 풀이) → 시간 복잡도 측면에서 좀 더 효율적이다.

두 배열을 순차적으로 꺼내면서 나온 선수들의 이름을 카운트 하는 방식은 어떨까?

HashMap에 Key값으로 선수의 이름을 넣고, Value값으로 선수의 이름이 나온 횟수를 카운트 하자.

그 후 다시 반복문을 돌리면서 나온 선수의 이름을 차감하면 혼자만 값이 다른 선수가 완주하지 못한 선수가 된다.

import java.util.HashMap;
    
class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> hashmap = new HashMap<>();
        
        for(String name : participant) {
            hashmap.put(name, hashmap.getOrDefault(name, 0) + 1);
        }
        
        for(String name : completion) {
            hashmap.put(name, hashmap.get(name) - 1);
        }
            
        for(String name : hashmap.keySet()) {
            if(hashmap.get(name) != 0) {
                return name;
            }
        }
            
        return "";
    }
}

HashMap<String, Integer> hashmap = new HashMap<>();
→ HashMap 선언부이다. key를 String 타입으로, value를 Integer 타입으로 선언했다.

for(String name : participant)
→ particiant의 값을 하나씩 꺼내어 name에 넣는다.

hashmap.put(name, hashmap.getOrDefault(name, 0) + 1);
→ hashmap.getOrDefault(name, 0) + 1 → name key가 HashMap에 있으면 그 key의 value값을 반환한다. 없으면 0을 반환한다. 이후 1을 증가시킨다.
→ hashmap.put() → 위에서 나온 값을 HashMap의 key 값이 일치하는 곳에 저장한다.

for(String name : completion)
→ completion의 값을 하나씩 꺼내어 name에 넣는다.

hashmap.get(name) - 1
→ HashMap에서 name key에 해당하는 value 값을 가져온다. 가져온 값에는 1을 차감한다.

hashmap.put(name, hashmap.get(name) - 1);
→ 위에서 나온 값을 다시 name key에 일치하는 value 값에 넣는다.

for(String name : hashmap.keySet())
→ HashMap의 key값들을 추려서 Set<String>형태로 변환한다. → 그 후 name에 하나씩 저장한다.

if(hashmap.get(name) != 0)
return name
→ name의 값과 일치하는 HashMap의 key가 가지고 있는 value 값이 0이 아니면, 해당 name을 return한다.

return "";
→ 컴파일 에러 방지용 return

시간 복잡도: O(n)

---

코드 구현

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for(int i = 0; i < completion.length; i++) {
            if(participant[i].equals(completion[i]) == false) {
                return participant[i];
            }
        }
        
        return participant[participant.length - 1];
    }
}

---

배우게 된 점

문자열 배열도 정렬이 가능하다는 사실을 알았다.

HashMap의 기본적인 사용법에 대해 익힐 수 있었다.