[프로그래머스] 완주하지 못한 선수

1. 문제 설명

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

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

 

 

 

2. 제한사항

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

 

 

3. 입출력 예

participant	completion	return
[leo, kiki, eden]	[eden, kiki]	leo
[marina, josipa, nikola, vinko, filipa]	[josipa, filipa, marina, nikola]	vinko
[mislav, stanko, mislav, ana]	[stanko, ana, mislav]	mislav

 

 

 

4. 입출력 예 설명

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

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

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

 

 

 

 

5. 문제 해석 및 회고

위 문제는 배열을 비교하여 participant 배열에는 없는 것을 찾는 문제였다. 지금까지 C++위주로 학습하다 JAVA로 풀이하려니 JAVA 자료형에 대한 이해가 부족한 것을 많이 느꼈다. 다음은 내가 몰랐던 부분이거나, 짚고 넘어가야 할 부분이다.

 

• Java에서 Map 자료형은 같은 key가 입력될때, 기존 값을 덮어쓰기 해버린다
• String[] 자료형과 ArrayList자료형의 길이(사이즈)를 구할때는 각각 .length와 .size()를 사용한다.
• Map자료형을 탐색시, Iterator를 사용하여 키 값을 기준으로 탐색이 가능하다.

맨 처음 풀때는, string값 하나하나를 .equals()로 비교하다보니 정답은 나왔지만 효율성에서 매우 꽝이었다. 효율성을 위해 고민한 결과, 탐색시, 나왔던 값과 나오지 않은 값에 대한 판단을 HashMap에 <key, value>로 담아 관리하게 되면 string 비교를 하지 않고 등장 횟수 처리를 통해 조금 더 효율적으로 처리할 수 있을 것이라 판단했다.

위 생각을 확장하면, 데이터가 모두 다른 사람으로 주어진다면, 0 or 1로 처리가 가능하다. 그러나 이 문제는 동명이인이 있을 수 있기 때문에, 이에 대한 처리도 필요하였다. 그래서 달릴 거리가 남아 있는 상태를 1 이상의 수, 완주하여 complete한 상태를 0으로 하여 문제를 풀기로 마음먹었다. 풀이 코드는 다음과 같다.

 

 

 

 

6. 풀이 코드

import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;

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

        String answer = new String();
        Map<String, Integer> map = new HashMap<>();
        
        //마라톤 참가자의 map 등록, 동명이인은 1번 더 같은 거리를 뛰는 것으로 간주하고, 동일인 취급.
        for(int i=0;i<participant.length;i++){
            if(map.get(participant[i])==null){
                map.put(participant[i], 1);
            }else{
                map.put(participant[i], map.get(participant[i])+1);
            }
        }
        
        //완주자는 완주거리에 대한 값 빼줌.
        for(int i=0;i<completion.length;i++){
                map.put(completion[i], map.get(completion[i])-1);
        }

		//아직 뛸 거리가 남은 사람을 탐색한다.
        //완주할 거리가 남아있으면, 1이상의 값을 나타낸다.
        //완주 하였으면 더이상 뛸 거리가 없으므로 0으로 표기한다.
        Iterator<String> iter = map.keySet().iterator();
        while(iter.hasNext()){
            answer = iter.next();
            //완주하지 못한 사람이 걸리면 바로 값을 return 한다.
            if(map.get(answer)!=0){
                return answer;
            }
        }
        
        //while문에 안걸리면 마지막 Map 원소의 key값이 덜 뛴 사람이다.
        return answer;
    }
}

 

 

 

 

7. 출처

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