자바 자료구조#10. Map 연습문제_완주하지 못한 선수

문제

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

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

• 제한사항
  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.
• 입출력 예
  참여 : ["mislav", "stanko", "mislav", "ana"] | 완주 : ["stanko", "ana", "mislav"]
  "mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

---

나의 풀이 --> 효율성 테스트 통과 실패

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        String answer = "";
        
        List<String> participantList = Arrays.asList(participant);
        List<String> completionList = Arrays.asList(completion);
        List<String> completionList2 = new LinkedList<>(completionList);
        
        String looser = "";
        
        for (String name : participantList) {
            
            if (!completionList2.contains(name)) {
                looser = name;
            } else {
                completionList2.remove(name);
            }
        }
        
        return looser;
    }
}

---

강의 풀이

1. List 활용 --> 효율성 테스트 통과 실패

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
    	
        List<String> players = new LinkedList<>();
        
        for (String p : participant) players.add(p);
        for(String c : completion) players.remove(c); // 시간이 가장 오래 걸리는 부분
        
        return players.get(0);
    }
}

2. Map 활용

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
    	
        Map<String, Integer> players = new HashMap<>();
        
        // O(n) --> 전체 시간복잡도
        for (String p : participant) {
        	players.put(p, players.getOrDefault(p, 0) + 1);
        }
        
        // O(n)
        for (String c : completion) {
        	int count = players.get(c) - 1;
            if (count == 0) {
            	players.remove(c);
            } else {
            	players.put(c, count);
            }
        }
        
        // O(1)
        return players.keySet().iterator().next();
    }
}

3. Array 활용

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
    	// O(nlogn) --> 전체 시간복잡도
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        // O(n)
        String name = "";
        for (int i = 0; i < completion.length; i++) {
        	if (!articipant[i].equals(completion[i])) {
            	name = participant[i];
            }
        }
        
        return name;
    }
}