[Lv.1] 완주하지 못한 선수

언어: java

 

 

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 `participant`와 완주한 선수들의 이름이 담긴 배열 `completion`이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해 주세요.

 

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

`completion`의 길이는 `participant`의 길이보다 1 작습니다.

참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

참가자 중에는 동명이인이 있을 수 있습니다.

 

 

---

 

📌 풀이(1/3) - ArrayList

`ArrayList`의 `indexOf()`는 앞에서부터 검색해 일치하는 객체 중 가장 먼저 발견한 객체의 인덱스를 반환한다. 찾지 못하면 -1을 반환한다. 따라서 `indexOf()`로 해당 객체의 인덱스를 찾은 뒤 해당 인덱스를 사용해 `remove()`를 하려고 했다.

그러나 `remove()` 메서드는 `indexOf()`처럼 앞에서부터 검색해 일치하는 객체 중 가장 먼저 발견한 객체 하나를 삭제하므로 위의 과정이 불필요하다. completion의 길이는 participant의 길이보다 1 작다는 것은 완주하지 못한 선수가 반드시 한 명은 존재한다는 의미로, `p.get()`에 던져줄 매개변수를 0으로 두어도 `p` 내의 객체가 반드시 하나는 존재하기 때문에 null이 나오지 않는다.(검증할 필요 없음)

 

//	정확성 통과, 효율성 실패(시간 초과)

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {

        List<String> p = new ArrayList<>(Arrays.asList(participant));
        
        for(int i = 0; i < completion.length; i++){
            p.remove(completion[i]);
        }
        
        return p.get(0);
        
    }
}

 

그러나 `ArrayList`를 사용하면서 for문으로 중간 인덱스 삭제를 몇 번이나 반복하는 것은 좋은 방법이 아니다. `remove(Object o)` 메서드의 경우 내부에서 null이 아닌지 확인 후에 `get(o)` 메서드를 부르고 boolean으로 수행 결과(지워졌는지 아닌지)를 뱉어내기 때문에 시간 복잡도는 O(n)으로 성능이 나쁘다고 할 수는 없으나, `ArrayList`는 중간의 인덱스가 지워지게 되면 후 요소의 인덱스가 당겨지면서 배열의 복사가 일어나므로 성능 저하를 일으킨다. 

 

효율성 실패!

 

 

[자료구조] ArrayList - 배열의 단점을 보완한 자료구조

---

 

 

📌 풀이(2/3) - 배열(Arrays)

`completion`의 길이는 `participant`의 길이보다 항상 1이 작기 때문에 완주하지 못한 선수는 반드시 한 명이 존재한다. 그렇다면 두 배열 모두 정렬 후 하나씩 비교해 봤을 때 중간에 같은 인덱스이지만 다른 이름이라면, 완주 선수 목록에 참여 선수 이름이 없다는 뜻이 되므로  `participant`의 해당 인덱스 요소를 반환하면 된다. 

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for(int i = 0; i < participant.length; i++){
                if(!participant[i].equals(completion[i])){
                    return participant[i];
                }
        }
        
        return answer;
    }
}

 

그러나 `completion` 배열의 길이가 `participant`보다 항상 작기 때문에 인덱스 i가 계속 증가하여 `participant`의 마지막 인덱스를 가리키게 되는 경우 `completion[i]`는 반드시 없는 인덱스가 되므로 `ArrayIndexOutOfBoundsException`이 발생한다. 이 문제를 해결하기 위해 try - catch문을 작성하여 함수를 완성했다. 

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        
        for(int i = 0; i < participant.length; i++){
            try{
                if(!participant[i].equals(completion[i])){
                    return participant[i];
                }
            }catch(ArrayIndexOutOfBoundsException e){
                return participant[i];
            }
        }
        
        return answer;
    }
}

 

 

 

---

 

 

📌 풀이(3/3) - HashMap

`participant` 목록에는 동명이인이 존재하므로 `HashSet`에 값을 넣으면 값이 사라지게 된다. 따라서 `HashMap`을 사용하여 동명이인의 카운트를 값으로 보관하기로 했다. `HashMap`에 참가자의 이름을 넣되, 이미 `HashMap`에 존재하는 이름이라면 해당 이름을 키로 가진 값을 1 증가시킨다. 여러명의 동명이인도 카운트할 수 있다.

이제 완주한 사람을 카운트에서 제외시킨다. `participant`는 `completion` 집합을 포함하고 있기 때문에 `completion`에 존재하는 이름이라면 반드시 `HashMap`에 해당 이름의 키가 존재한다. 그러므로 `completion` 목록의 이름을 키로 가진 값을 1 감소시킨다.

이 과정을 거쳐 완주했다면 값이 0, 완주하지 못했다면 1 이상의 값을 가진다. (문제에서는 완주하지 못한 선수가 단 한 명이라고 했기 때문에 1이 존재할 것이다.) 값이 0이 아닌 키, 즉 선수의 이름을 반환한다. 

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Map<String, Integer> map = new HashMap<>();
        
        for(int i = 0; i < participant.length; i++){
            if(map.containsKey(participant[i])){
			map.put(participant[i], map.get(participant[i]) + 1);
            }else{
			map.put(participant[i], 1);
            }
        }
        
        for(int i = 0; i < completion.length; i++){
            map.put(completion[i], map.get(completion[i])-1);
        }
        
        for(int i = 0; i < participant.length; i++){
            if(map.get(participant[i]) != 0){
                return participant[i];
            }
        }
        
        
        return answer;
    }
}

 

Arrays보다 빠르게 성공!

 

 

 

 

프로그래머스