99클럽 코테 스터디 11일차 TIL(프로그래머스-완주하지못한선수)

완주하지 못한 선수

KeyWord: 효율성을 따진 HashMap
처음에 문제를 풀었을 때, HashMap, Set 키 값이 중복이 되지 않기에, 중복이 ArrayList를 사용해서 문제를 풀었다.
그런데, 문제는 풀었는데, 정답은 맞았지만, 효율성에서 떨어진다고 한다.
그 이유는 remove 시간 복잡도가 O(N)이기에 효율성에 떨어진다고 했다. 해결을 하려면 Map을 사용하지만, 중복값이 걸리기에, Value값을 카운트로 해서 제거하는 식으로 가져가는 풀어야한다고 해서, 다음과 같이 해결.

효율성 문제에서 걸림.
이 접근 방식의 총 시간 복잡도는 O(n * m)으로, completion 배열의 각 요소를 participant 리스트에서 찾아 제거할 때마다 전체 리스트를 순회해야 합니다. 이로 인해 participant와 completion의 길이가 커질수록 성능이 급격히 떨어지게 됩니다.

 public String solution(String[] participant, String[] completion) {
            List<String> list = new ArrayList<>();
            for (String N : participant) {
                list.add(N);
            }
            for(String S : completion){
                list.remove(S);
            }
            String answer = list.toString().replace("[","").replace("]","");
            return answer;
        }

HashMap을 써서 해결 해야 효율성 문제가 해결.
이 접근 방식의 총 시간 복잡도는 O(n + m)입니다. HashMap을 사용하여 participant와 completion 배열을 한 번씩만 순회하기 때문에, 이전 코드보다 훨씬 효율적입니다. n과 m이 커질수록 HashMap을 사용한 방식이 훨씬 빠릅니다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
            Map<String, Integer> map = new HashMap<>();
            String answer = "";

            for(String p : participant){
                map.put(p, map.getOrDefault(p,0)+1);
            }
            for(String c :completion){
                map.put(c, map.get(c)-1);
            }
            for(String key : map.keySet()){
                if(map.get(key)!=0 ){
                    answer = key;
                }
            }
            return answer;
        }
}