[코딩테스트 연습, 프로그래머스, Java] - 완주하지 못한 선수

💡문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

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

 

💡제한 사항

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

💡문제 단순화하기

participant에는 있고 completion에는 없는 한 명을 찾아라!!

 

💡풀이

1. Sorting / Loop을 활용한 solution

• 두 list를 sorting 한다.
• completion list의 length만큼 돌면서 participant에만 존재하는 한 명을 찾는다.
• List를 전부 다 뒤져도 답이 없다면, participant의 마지막 주자가 완주하지 못한 선수이다.

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        //1. 두 배열을 정렬한다.
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        //2. 두 배열이 다를 때까지 찾는다.
        int i=0;
        for(;i<completion.length; i++)
        	if(!participant[i].equals(completion[i]))
        		break;
        
        //3. 여기까지 왔다면, 마지막 주자가 완주하지 못한 선수다.
        return participant[i];
    }
}

 

2. Hash를 활용한 solution

• Key에 선수의 이름을, Value의 Count를 갖는 HashMap을 만든다.
• completion에 존재하는 선수들의 Hash를 뺀다.
• Value가 남아있는 선수가 완주하지 못한 선수이다.

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
    	
    	String answer = "";
        
    	//1. Hash map을 만든다. (participant)
    	HashMap<String, Integer> map = new HashMap<>();
    	for(String player : participant)
    		//동명이인이 있을 수 있기 때문에 이전에 있던 값+1
    						//map에서 player라는 key를 가진 값을 가져와라,
    						//만약에 없으면 그냥 0을 달라.
    		map.put(player, map.getOrDefault(player, 0)+1);
    	
    	//2. Hash map을 뺀다. (completion)
    	for(String player : completion)
    		map.put(player, map.get(player)-1);
    	
    	//3. value가 0이 아닌 마지막 주자를 찾는다.
    	
    	//map이 가지고 있는 key를 하나씩 꺼낸다.
    	for(String key : map.keySet()) {
    		if(map.get(key)!=0) {
    			answer = key;
    			break;
    		}
    	}
    	return answer;
    }
}