[프로그래머스] Lv1. 완주 못한 선수.

작가 pikisuperstar 출처 Freepik

<링크>

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

프로그래머스

 

<문제 설명>

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

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

 

- 제한 사항

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

 

<문제 해석>

0. 마라톤을 완주하지 못한 선수의 이름을 answer로 return해주면 된다.

1. 선수의 수 범위는 1~10만명, 간격이 꽤 크다. -> 단순 반복문으로 처리하기에 비효율적일 수 있음.

2. 완주 못한 선수는 단 1명.

4. 마라톤 참가자는 동명이인이 있을 수 있음. -> 해당 문자열을 찾아 삭제하거나 카운트할 때 조심해야 함.

 

처음에는 각 배열을 정렬 후 이름을 서로 매칭하여 하나씩 삭제해주며, 마지막 남는 이름 하나를 리턴해줄까 생각했다.

근데 범위가 10만명이라 일일이 반복문하기에 비효율적일 것 같다 생각하기도 했고,

해싱을 사용하여 풀라는 문제기도 해서 해시맵을 사용하기로 결정함.

 

<문제 풀이>

해시맵을 사용해서 key값에는 선수의 이름, value에는 해당 이름의 인원수를 카운트해 해시맵을 구성

(동명이인이 있어, 이름당 값을 1로 지정하지 않고, 카운트해주기로 함)

참가선수 명단을 처음 카운트 +1 해주고, 완주시 -1 해준다. 

value가 1이라면 1명이 현재 마라톤중이고, 0이라면 해당 이름의 선수 모두 완주

해시맵을 루프했을 때 value값이 1인 선수 한명의 이름을 return 해주는 식으로 풀어보았다.

 

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        // comp는 part보다 길이 1 짧음
        String answer = ""; // answer = 완주 못한 선수
        
        // 1. 해시맵에 part 추가 key는 선수, value는 선수카운트
        HashMap<String, Integer> map = new HashMap<>();
        for(String p : participant){
            map.put(p, map.getOrDefault(p, 0) + 1);
        }
        // 2. comp를 반복, 완주했으면 카운트 마이너스
        for(String p : completion){
            map.put(p, map.get(p) - 1);
        }
        
        // 3. value가 0이 아닌 선수 1명만 남으니 return
        for(String key : map.keySet()){
            if(map.get(key) != 0){
                answer = key;
                break;
            }
        }
        return answer;
    }
}

 

 

<다른 사람의 풀이>

풀이를 보니 거의 똑같이 푼 사람이 제일 많았다.

거의 유사하니 코드는 생략.

좋아요가 제일 많은 풀이의 댓글에 보니, 

효율성 면에서 좋은 답안이 아닙니다. keySet하고 또 get하는 건 매우 비효율적인 코드입니다. get할 때마다 계속 HashMap을 search하니까요. key, value를 같이 가져올 때는 항상 entrySet을 사용해야 해요.

라고 피드백이 달려있었다. 

 

그래서 더 효율적으로 리팩토링 해보려 한다.

 

주석 3번부분만 조금 수정해주면 좋을 것같다.

 

import java.util.HashMap;

class Solution {
	public String solution(String[] participant, String[] completion) {
    	// comp는 part보다 길이 1 짧음
        String answer = ""; // answer = 완주 못한 선수
        
        // 1. 해시맵에 part 추가 key는 선수, value는 선수카운트
        HashMap<String, Integer> map = new HashMap<>();
        for(String p : participant){
            map.put(p, map.getOrDefault(p, 0) + 1);
        }
        // 2. comp를 반복, 완주했으면 카운트 마이너스
        for(String p : completion){
            map.put(p, map.get(p) - 1);
        }
        
        // 3. value가 0이 아닌 선수 1명만 남으니 return
        // 변경된 부분
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
        	if(entry.getValue() != 0) {
        		answer = entry.getKey();
            	break;
    		}
		}
        
	return answer;
	}
}

 

---

- 리팩토링 전

 

- 리팩토링 후

 

시간과 용량을 보면 별차이가 없어보인다. 오히려 늘어난 것도 있지만, 

찾아보니 각 키에 대해 get()을 호출하는 것이 용량이 커질 수록 비효율적이라 한다.

 

keySet()을 사용하고 각 키에 대해 get()을 호출하는 것은 실제로 불필요한 해시 검색을 추가로 발생시키기 때문에 비효율적입니다. 각 키에 대해 해시맵을 한 번 더 검색하기 때문에, 키의 개수가 많을수록 성능 저하가 일어날 수 있습니다.
효율적으로 키와 값을 동시에 검색하려면 entrySet() 메서드를 사용하는 것이 좋습니다. entrySet()은 Map의 Entry 객체를 Set으로 반환하며, 각 Entry에는 키와 값이 함께 포함되어 있어서 별도의 검색 없이 바로 접근할 수 있습니다.

gpt에게 질문해보았다.

entrySet 사용하는 것도 열심히 이해해야겠다. 

 

이상

오늘은 여기까지!