[Java : 프로그래머스] 완주하지 못한 선수

📝 문제

https://programmers.co.kr/learn/courses/30/lessons/42576?language=java

🎯 풀이

❌ ArrayList를 이용한 풀이

1. ArrayList에 참가자 명단을 삽입한다.
2. ArrayList에서 완주자들을 제거한다.

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        List maratoner = new ArrayList();
        for(String part : participant) maratoner.add(part);
        for(String comp : completion) maratoner.remove(comp);
        return (String)maratoner.get(0);
    }
}

# 정확성  테스트
테스트 1 〉	통과 (0.04ms, 52.4MB)
테스트 2 〉	통과 (0.05ms, 52.8MB)
테스트 3 〉	통과 (3.22ms, 53.1MB)
테스트 4 〉	통과 (13.21ms, 53.9MB)
테스트 5 〉	통과 (13.39ms, 54MB)

# 효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)

정확성은 100%지만, 효율성이 꽝이다!
ArrayList.remove 메소드로 요소 삭제 후
남은 요소간 재정렬에서 생기는 오버헤드가 어마어마한걸로 보인다.
이번엔 해시를 이용해보자.

---

⭕ HashMap을 이용한 풀이

1. HashMap에 참가자를 등록한다.
   • 만일 동명이인이 있을 경우, Value를 더한다.
2. HashMap에 완주자를 기록한다.
   • Key로 이름을 찾아내서, Value를 뺀다.
3. HashMap에서 Value가 1 이상인 Key를 찾아 반환한다.

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> maratoner = new HashMap<>();
        for(String person : participant) {
            if(maratoner.containsKey(person)) // 동명이인이라면?
                // value 증가
                maratoner.replace(person, (int)maratoner.get(person)+1);
            else // 처음 보는 이름이라면 등록
                maratoner.put(person, 1);
        }
        for(String person : completion) // 완주자는 value 감소
            maratoner.replace(person, (int)maratoner.get(person)-1);

        String answer = "";
        for(Map.Entry person : maratoner.entrySet()) {
            if((int)person.getValue() > 0){ // value가 0보다 크면?
                answer = (String) person.getKey();  // 미완주자다!
                break;
            }
        }
        return answer;
    }
}

# 정확성  테스트
테스트 1 〉	통과 (0.07ms, 53.2MB)
테스트 2 〉	통과 (0.08ms, 51.9MB)
테스트 3 〉	통과 (0.63ms, 52.2MB)
테스트 4 〉	통과 (1.29ms, 54.2MB)
테스트 5 〉	통과 (1.09ms, 54.9MB)

# 효율성  테스트
테스트 1 〉	통과 (34.35ms, 81.6MB)
테스트 2 〉	통과 (88.20ms, 89MB)
테스트 3 〉	통과 (123.68ms, 98MB)
테스트 4 〉	통과 (83.60ms, 96.5MB)
테스트 5 〉	통과 (84.74ms, 95.1MB)

👏👏👏