<링크>
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 사용하는 것도 열심히 이해해야겠다.
이상
오늘은 여기까지!
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] Lv1.숫자짝꿍.java (0) | 2023.12.14 |
---|---|
[프로그래머스]Lv1. 옹알이(2). JAVA (1) | 2023.12.07 |
[프로그래머스, JAVA, Lv1, KAKAO] 다트 게임 (0) | 2023.12.04 |
[프로그래머스, JAVA, Lv1, KAKAO] 실패율 (0) | 2023.12.01 |
[프로그래머스, JAVA, Lv1] 덧칠하기 (1) | 2023.11.29 |