코드가 짧다고 효율이 좋은 것은 아니다.

프로그래머스 42576번 [완주하지 못한 선수] 문제를 풀었다.
두 개의 배열이 주어지는데,
participant 배열에는 참가자 전원이,
completion 배열에는 완주한 인원이 들어있다.
이 중 완주하지 못한 사람을 찾아 return하면 된다.

* 미완주자는 한 명이다.

---

1. 완주자를 ArrayList에 담아서, 그 List에 존재하지 않는 참가자 찾기

참가자 배열(participant)를 순회하며, 이름을 완주자 List(completionList)에서 찾을 때마다 지워준다.

participant : ["leo", "kiki", "eden"]
completion: ["eden", "kiki"]

일 때,
완주자 List에 leo는 존재하지 않기 때문에 indexOf("leo")시 -1이 돌아온다. ==> 그 사람이 미완주자이다.
kiki, eden은 존재하기 때문에 List에서 remove된다.

🐚 소스 코드

    public static String solution(String[] participant, String[] completion) {
        String answer = "";

        List<String> completionList = Arrays.stream(completion).collect(Collectors.toList());

        for (String name : participant){                	// 참가자 전원 배열을 순회하면서
            int idx = completionList.indexOf(name);
            if (idx > -1) completionList.remove(idx);   // 현재 참가자가 완주 목록에 있으면 (index가 -1보다 크면) List에서 삭제
            else answer = name;                         		// 그렇지 않으면 (index가 -1이면) 그 사람은 미완주가 된다.
        }

        return answer;
    }

 

🪸 채점 결과

답이 나오긴 하지만 효율성 0점 받았다 ...

---

2. 참가자를 HashMap에 담아서 완주자 목록에 있는 사람의 value 빼주기

participant : ["leo", "kiki", "eden"]
completion: ["eden", "kiki"]

일 때,
처음 반복문을 거쳐 만들어지는 참가자 HashMap은 {leo=1, eden=1, kiki=1}이다.
(동명이인이 있다면 value가 올라간다.)

완주자 배열(completion)을 순회하면서, 완주자 목록에 있는 사람들의 value를 -- 해주면
{leo=1, eden=0, kiki=0}
미완주자를 제외한 모든 사람들의 value는 0이 된다. ==> value가 0이 아닌 사람이 미완주자이다.

map의 Entry를 Iterator로 순회하며, value가 0이 아닌 key를 찾아주었다.

🐚 소스 코드

    public static String solution(String[] participant, String[] completion) {
        String answer = "";

        Map<String, Integer> participantMap = new HashMap<>();	// 참가자 목록 Map을 생성
        for (int i = 0; i < participant.length; i++) {	// 참가자 배열을 순회하면서
            if (participantMap.get(participant[i]) != null) {	// Map에 현재 참가자가 있으면 (동명이인) value++
                participantMap.put(participant[i], participantMap.get(participant[i]) + 1); 
            } else {	// 현재 Map에 참가자가 없으면 value를 1로 추가
                participantMap.put(participant[i], 1);	
            }
        }

        for (int i = 0; i < completion.length; i++) {   // 완주자 배열을 순회하면서, 완주자의 value를 1씩 빼준다.
            participantMap.put(
                completion[i], participantMap.get(completion[i]) - 1
            );
        }   // -> 완주하지 못 한 사람의 value만 0이 아닐 것이다.

        Set<Entry<String, Integer>> entrySet =  participantMap.entrySet();
        Iterator<Entry<String, Integer>> iterator = entrySet.iterator();

        while(iterator.hasNext()) { // iterator로 map을 순회하면서, value가 0이 아닌 (미완주) 사람 찾기
            Entry<String, Integer> currentEntry = iterator.next();
            if (currentEntry.getValue() != 0) return currentEntry.getKey();
        }

        return answer;
    }

🪸 채점 결과

---

3. 이유를 생각해봤당

1번의 경우에는 for문(O(n)) 안에서 또 indexOf(O(n)), remove(O(n))를 자꾸 처리하기 때문에, 데이터가 커질 수록 효율이 떨어지는 것으로 보인다. (최대 인원 100,000명)

반면에 2번은 최대 시간복잡도가 O(n)이다.
HashMap은 put(O(1))과 get, getValue, getKey 등 해시테이블을 이용한 빠른 검색(O(1))이 이루어지기 때문이다.

시간복잡도를 생각하지 않고 문제를 풀어도 해결은 되지만, 이번 문제는 효율성 체크까지 있어서 다시 한 번 생각해볼 수 있는 계기가 되었다.😉