Hash함수에 대해 이해도를 높이기 위해 Hash문제를 다시 풀어보았다.
나는 처음에 해시를 몰라 배열로 접근하였지만, 해시를 사용하면 속도나 효율성 측면에서 더 나은것 같아서 다시 해시를 정확히 이해할 때 까지 차근차근 문제를 접해보겠다.
문제설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution함수를 작성해주세요.
제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예
입출력 예 설명
예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
이렇게 문제가 있고
나는 해시맵을 적용하여 아래와 같은 코드로 접근하였다.
class Solution {
public String solution(String[] participant, String[] completion) {
int cnt=0;
HashMap<String,Integer> hm = new HashMap<String,Integer>();
for(String i : participant) { //참가자 명단을 키값으로 벨류값을 카운팅시키면서 벨류값으로 차이를 주려고 함
hm.put(i, cnt++);
if(hm.containsKey(i)) { //중복된 키 값이 있으면 그 키 값이 리턴되리라 생각하고 작성
return i;
}else{
continue;
}
}
for(String j : completion) {
hm.remove(j); // 해시맵에 있는 participant 키들을 completion값들과 같으면 제거하여
} // 제거되지 못한 참가자가 완주하지 못한 참가자이기 때문에
String result = hm.keySet().iterator().next(); //남은 키값을 리턴
return result;
}
}나는 이렇게 접근하였지만 테스트케이스를 거의 통과하지 못했다.
hashmap에 대한 이해가 적었다고 생각한다.
먼저 내가 놓친 것은
put함수는 key값이 같으면 value값이 덮어씌워진다.
또 containsKey함수를 제대로 사용하지 못했다.
containsKey(?)함수는 인자로 보낸 ? 값이 KEY값에 있으면 true 없으면 false를 반환한다.
그러나 위 코드에서 나는 put한 후 인자값을 비교한다. 당연히 put 후 같은 것을 비교하니 true만 나올것이다.
그래서 나는 다른 사람의 코드를 참고하여 다시 공부하였다.
아래는 다른 사람이 짜낸 아죽 간결한 코드이다.
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
HashMap<String, Integer> hm = new HashMap<>();
for (String i : participant) hm.put(i, hm.getOrDefault(i, 0) + 1);
for (String i : completion) hm.put(i, hm.get(i) - 1);
for (String key : hm.keySet()) {
if (hm.get(key) != 0){
answer = key;
}
}
return answer;
}
}여기서는 나처럼 넣었다 지웟다가 아닌
hashmap이 key값이 중복되면 덮어쓰기 되는 성질을 아주 잘 이용한 것 같다.
또 getOrDefault 함수를 사용하였는데 무엇인지 몰라서 알아보았다.
getOrDefault(키,default값) 함수는 찾고자 하는 키가 존재하면 해당키의 값를 반환하고 없으면 default값을 반환한다.
위 코드는 처음 put할때 value를 0으로 세팅하면서 중복되는 key가 있으면 기본 value에 +1 해주는 방식이다.
이러면 중복이 없이 한개씩 put 이 적용된 key값의 value는 모두 1이 되고 만약 key값이 중복된 값이 있으면 중복된 개수만큼 + 된다.
그래서 또 competirion 값들을 key로 다시 집어 넣으면서 participant 키의 value값에 -1 해주면서 중복없이 한개씩 있던 키들의 값을 모두 0으로 만들어주었고, 만약 중복이 있던 key라면 -1을 하더라도 1 이상이기 때문에
마지막에 hashmap에서 value가 0이 아닌 것을 answer에 넣어 return해준 것이다.
설명을 잘 하지못해서 너무 주저리주저리 인것 같다... ㅠ
아무튼 이렇게 hashmap에 조금이나마(?) 익숙해져가는듯 하다!!
다른 방법들도 참고하면서 익혀나가도록 하자!!😁😁😁
