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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

접근 방법 및 풀이

제한 사항에서 동명이인이 존재 한다 하였기에 동명이인이 모두 완주 하거나 동명이인 중에 한명이 완주를 하지 못한 상황을 고려

이름이 중복을 고려 해야 하니 set 보다는 list를 사용

import java.util.*;

/**
 * 정확성 통과
 * 효율성 통과하지 못함
 */
public class Q30_42576 {
    public String solution(String[] participant, String[] completion) {
        List<String> participantList = new ArrayList<>(Arrays.asList(participant));
        for (String completionName : completion) {
            int index = participantList.indexOf(completionName);
            if (index > -1) {
                participantList.remove(index);
            }
        }
        return participantList.get(0);
    }
}

정확성 테스트를 모두 통과 하였으나 효율성 테스트를 모두 통과하지 못함

 

이유는 ArrayList의  indexOf, remove 메서드가 HashMap의 containsKey, remove에 비해서 성능이 좋지 못함

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Q30_42576Test {
    private static final String VALUE = "VALUE";

    /**
     * map, list 성능 테스트
     */
    @Test
    public void test() {
        final int MAX = 100000;
        List<String> list = new ArrayList<>();
        Map<String, String> map = new HashMap<>();

        long start = 0;
        long end = 0;

        start = System.currentTimeMillis();
        for (int i = 0; i < MAX; i++) {
            list.add("" + i);
        }
        end = System.currentTimeMillis();
        System.out.println("list add: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        for (int i = 0; i < MAX; i++) {
            map.put("" + i, VALUE);
        }
        end = System.currentTimeMillis();
        System.out.println("map add: " + (end - start) + "ms");
        System.out.println("======");

        start = System.currentTimeMillis();
        for (int i = 0; i < MAX; i++) {
            list.indexOf("" + i);
        }
        end = System.currentTimeMillis();
        System.out.println("list indexOf: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        for (int i = 0; i < MAX; i++) {
            list.contains("" + i);
        }
        end = System.currentTimeMillis();
        System.out.println("list contains: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        for (int i = 0; i < MAX; i++) {
            map.containsKey("" + i);
        }
        end = System.currentTimeMillis();
        System.out.println("map containsKey: " + (end - start) + "ms");
        System.out.println("======");


        start = System.currentTimeMillis();
        for (int i = 0; i < MAX; i++) {
            list.remove("" + i);
        }
        end = System.currentTimeMillis();
        System.out.println("list remove: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        for (int i = 0; i < MAX; i++) {
            map.remove("" + i);
        }
        end = System.currentTimeMillis();
        System.out.println("map remove: " + (end - start) + "ms");
    }
}

위 코드로 성능 테스트를 해보면 다음과 같은 결과

 

list add: 12ms
map add: 22ms
======
list indexOf: 7294ms
list contains: 7366ms
map containsKey: 8ms
======
list remove: 482ms
map remove: 9ms

 

ArrayList를 HashMap으로 수정

import java.util.*;

/**
 * 정확성 통과
 * 효율성 통과
 */
public class Q30_42576 {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> participantMap = new HashMap<>();
        for (String name : participant) {
            participantMap.put(name, participantMap.getOrDefault(name, 0) + 1);
        }

        for (String name : completion) {
            int count = participantMap.get(name);
            if (count == 1) {
                participantMap.remove(name);
            } else {
                participantMap.put(name, count - 1);
            }
        }

        return participantMap.keySet().toArray(new String[0])[0];
    }
}

정확성 테스트와 효율성 테스트를 모두 통과