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

✔️ 문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

✔️ 입출력 예

 

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

 

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

 

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

✔️ 제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

 

✔️ 코드구상

participant를 List로 받은 후 completion의 length만큼 순회하며 contains를 통해 포함한다면 

List에서 삭제한 후 남은 1명을 answer로 반환하면 되겠다고 생각했다...

 

✔️ 1차 코드 (실패)

• 정확성은 다 맞았지만 효율성에서 다 시간초과가 나왔다...
• 시간 복잡도가 그렇게 오래 걸리지 않을거 같은데 worst case에서 List를 삭제하는 과정이 오래 걸릴 수도 있겠다 싶었다.

import java.util.*;

public class Solution {
    public String solution(String[] participant, String[] completion) {
        ArrayList<String>  parArr = new ArrayList<>(Arrays.asList(participant));
        String answer = "";
        for (int i = 0; i < completion.length; i++) {
            if(parArr.contains(completion[i])) {
                parArr.remove(completion[i]);
            }
        }

        answer = parArr.get(0);

        return answer;
    }
}

 

✔️ 2차 코드 (성공)

• 문제 유형이 해쉬길래 HashMap을 사용했는데 해결됐다..
• for문은 이게 더 많이 들어가는데 List에서의 삭제과정이 아닌지 효율성도 통과했다.

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++) {
            if(map.get(completion[i]) == 1) {
                map.remove(completion[i]);
            } else {
                map.put(completion[i], map.get(completion[i]) - 1);
            }
        }

        String imcompletion = map.keySet().toString();
        answer = imcompletion.substring(1, imcompletion.length() - 1);

        return answer;
    }
}

 

📄 원문

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