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

문제

 

분석

• List, Map 어떤걸로 풀어야 될까 고민을 해봐야 한다.
• 문제 분류가 Map 이기때문에 Map을 써야 하는데 왜 그럴까?
  
  
• List 로 구현하면 최소 탐색 시간이 O(N) 이 걸린다.
• 하지만 Map의 경우 Tree 구조를 가지고 있기 때문에 O(h) 트리의 높이 만큼 걸린다.
• 하지만 최악의 경우 N 이 걸리기도 한다.

 

• 그렇기 때문에 Map 을 쓰자 

 

 

구현1 (효율성 실패케이스)

    import java.util.*;

    class Solution {
        public String solution(String[] participant, String[] completion) {
            String answer = "";
            int index = 0;

            ArrayList<String> completionList = new ArrayList<>(Arrays.asList(completion));
            for (int i = 0; i <participant.length; i++) {
                if (completionList.contains(participant[i])) {
                    completionList.remove(participant[i]);
                } else {
                    answer = participant[i];
                }
            }
            return answer;
        }
    }

 

구현1 결과

 

 

 

구현2 (효율성 통과)

    import java.util.*;

        class Solution {
            public String solution(String[] participant, String[] completion) {
                String answer = "";
                int index = 0;

                Map<String, Integer> participantMap = new HashMap<>();
                for (String participantString : participant) {
                    if (participantMap.containsKey(participantString)) {
                        int count = participantMap.get(participantString);
                        participantMap.replace(participantString, ++count);
                    } else {
                        participantMap.put(participantString,1);
                    }
                }

                for(String completionString : completion) {
                     if(participantMap.containsKey(completionString)) {
                         int count = participantMap.get(completionString);
                         if (count > 1) {
                             participantMap.replace(completionString, --count);
                         } else {
                             participantMap.remove(completionString);
                         }
                     }
                }

                Iterator<String> keys = participantMap.keySet().iterator();
                while (keys.hasNext()) {
                     answer = keys.next();
                     break;
                }
                return answer;
            }
        }

 

 

구현2 결과

 

 

생각해보기

만약 테스트중에 정확성은 백퍼센트지만 

효율성이 떨어지면 다른 자료구조를 생각해보자.