[완주하지 못한 선수] - 42576

 

 

문제 링크입니다.

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

코딩테스트 연습 - 완주하지 못한 선수

 

이 문제는 효율성 테스트가 중요합니다.

저는 처음에 자바 Collection 클래스인 ArrayList 로 접근을 했다가, 효율성 테스트에서 실패했습니다.

 

실패한 소스코드

public String solution(String[] participant, String[] completion) {
    String answer = "";
    List<String> list= new ArrayList<>();

    for (String s : participant)
        list.add(s);

    for (String s : completion) {
        if(list.contains(s)){
            list.remove(s);
        }
    }

    answer = list.get(0);
    return answer;
}

participant, compleion 배열의 길이가 최대 100000 까지입니다.

 

다음 for문을 봅시다.

for (String s : completion) {
    if(list.contains(s)){
        list.remove(s);
    }
}

list.remove(), list.contains() 의 시간복잡도가 각각 O(N) 이므로, 총 시간복잡도가 O(N^2)가 됩니다. 

N=100000 인 경우 시간복잡도가 O(10^10)까지도 갈 수 있는것이죠. 

 

 

> ArrayList

시간복잡도
add             : O(1)
remove          : O(n)
get             : O(1)
Contains        : O(n)
iterator.remove : O(n)
java 1.2에 추가, thread-safe 보장 안함
 특징 :  데이터 추가,삭제를 위해 임시 배열을 생성해 데이터를 복사
   - 대량의 자료를 추가/삭제시 복사가 일어 나게 되어 성능 저하를 일이킴
   - 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름

 

> HashMap

시간복잡도
get           : O(1)
containsKey   : O(1)
next          : O(h/n) h는 테이블 용량
java 1.2 에서 나옴
특징 : 순서에 상관없이 저장됨, Null을 허용한다. thread-safe 보장하지 않는다.

자료 출처: GrepIU

 

HashMap을 사용해서 문제를 풀어봅시다.

 

정답 소스코드

public String solution(String[] participant, String[] completion) {
    String answer = "";
    Map<String, Integer> map = new HashMap<>();
    for (String s : participant)
        map.put(s, map.getOrDefault(s,0)+1);

    for (String s : completion)
        map.put(s, map.getOrDefault(s, 0)-1);

    Iterator<String> it = map.keySet().iterator();

    while(it.hasNext()){
        String next = it.next();
        if(map.get(next) != 0){
            answer += next;
            break;
        }
    }

    return answer;
}

여기서는 map.get 의 시간복잡도가 O(1)이므로, 효율성이 높습니다.

주요 아이디어는 map의 key값으로 사람의 이름을, value 값으로 해당 이름의 인원 수를 넣는 것입니다.

 

문제 링크에서 예시 3번을 봅시다.

participant : ["mislav", "stanko", "mislav", "ana"]

completion : ["stanko", "ana", "mislav"]

 

맨 처음, participant 에서 참가자 이름이 중복될 경우, 동명이인이므로 인원수를 2명으로 쳐줍니다.

HashMap<String, Integer> map :

key	value
"mislav"	2
"stanko"	1
"ana"	1

 

그 후 completion 배열을 돌면서 완주한 선수의 이름을 받고, 그 숫자를 1씩 감소시켜줍시다.

key	value
"mislav"	1
"stanko"	0
"ana"	0

 

위와 같이 value를 Key를 이름으로 가지는 선수들의 인원수 로 설정, String 배열의 완주자 목록을 돌면서 해당 이름에 대한 value(인원 수)를 1씩 감소시켜줍니다. 

 

마지막에 map에서 value 값이 0이 아닌 선수 이름을 찾아서 출력해주면 되겠습니다.