[프로그래머스 42576] 99클럽 코테 스터디 2일차 TIL + Hash

두둥! 코테스터디 2일차!! 

오늘도 어제처럼 Hash 관련 문제다.

• 오늘의 문제

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

프로그래머스

 

• 나의 풀이

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        String answer = "";
        HashMap<String, Integer> map = new HashMap<>();
        
        for(String name : participant){
            map.put(name, map.getOrDefault(name, 0) + 1);
        }
        for(String name : completion){
            map.put(name, map.get(name)-1 );
        }
        
        for (String key : map.keySet()) {
            if (map.get(key) != 0) {
                answer = key;
                break;
            }
        }
        return answer;
    }
}

 

이번엔 힌트를 보고 풀었다ㅠㅠ 

 

 

• 알게 된 점

우선 두 배열이 주어졌으니, 두 배열을 비교하여 중복된 값을 제거하고 남은 선수의 이름만 리턴하면 되겠다! 라는 생각으로 접근을 했다. 중복 값 제거를 위해 처음에는 HashSet을 써서 풀려고 했다. 하지만 HashSet으로 풀자니, 동명이인 조건을 처리할 수가 없었다. 때문에 해당 문제는 HashMap을 활용해야 된다.

HashMap은 key, value 형태로 저장하기 때문에, key에는 참석한 선수의 이름을, value에는 참석자 수를 저장하면 된다.

(동명이인이 있기 때문에, 동명이인의 value는 아마 2 이상일 것이다.)

 

그리고 value를 저장할 때  map.getOrDefault(name, 0) + 1를 사용하여 저장한다.

Map의 getOrDefault(key, defaultValue) 메소드는 null 대신 기본 값을 반환할 수 있는 메소드이다. 아래 예제를 보면 이해가 빠를 것이다.

Map<String, String> map = new HashMap<>();

map.put("A", "봄");
map.put("B", "여름");
map.put("C", "가을");
map.put("D", "겨울");

System.out.println(map.get("E"));	 // 결과 : null
System.out.println(map.getOrDefault("A","없음")); // 결과 : 봄
System.out.println(map.getOrDefault("E","없음")); // 결과 : 없음

 

이 getOrDefault()를 이용해서 참석자 이름을 저장하는데, 참석한 선수의 각 이름들이 최초로 저장될 때는 ma에 key(참석자명)이 저장되어 있지 않으므로, value는 0이다. 때문에 +1을 해줘서 해당 참석자명의 참석자 수를 1로 만들어 준다. 이후 동명이인의 value는 기존 value에 +1씩 중가하게 되는 것이다.

 

* getOrDefault()를 쓰지 않으면 중복체크가 되지 않는다고 한다. HashMap의 put은 key가 존재하면 value를 새로운 값으로 바꿔주기 때문이다. 

 

다음으로 동일한 map에 completion(완주한 선수들의 배열)을 put해주는데, 이 때 key들은 중복처리가 되어 기존의 value값이 반환되므로, 중복된 경우 -1을 시켜준다. 즉 중복된 경우는 완주를 한 선수들이다. 

 

완주를 하지 못한 선수의 value는 1이므로, ( 문제에 단 한명의 선수만 완주하지 못한다고 나와있다.) 

value가 0이 아니거나, 0보다 큰 경우 등의 조건을 통해 해당 선수의 key값을 리턴하면 된다.

 

🎯 다른사람 풀이

import java.util.Arrays;
import java.util.Iterator;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

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

        Map<String, Long> participantMap = Arrays.asList(participant).stream()
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        for(String name : completion) {
            Long value = participantMap.get(name) - 1L;

            if(value == 0L) {
                participantMap.remove(name);
            } else {
                participantMap.put(name, value);
            }
        }

        return participantMap.keySet().iterator().next();
    }
}

무조건적인 stream사용은 좋지 않지만, 공부를 위해 stream 코드도 추가!

 

🎯 추가

프로그래머스에서 해당 문제의 다른사람 풀이들을 보다가 Eugene Chung 님이 쓰신 좋은 댓글이 있어서 추가한다.

 

마지막 부분에 keySet 후 get을 하는 것은 get할 때마다 계속 HashMap을 서칭하기 때문에 효율적이지 않은 코드라고 한다. key와 value를 같이 가져오는 경우 entrySet 사용을 권장한다고 한다!!

Entry의 getKey(), getValue()는 한번에 해당 entry의 key,value를 모두 불러온다. 이에 반에 HashMap의 get()은 hashcode(), equals() 등의 함수를 내부에서 실행하며 시간을 더 사용한다고 한다. 

 

- 글과 함께 제시해주신 참고 글 : https://stackoverflow.com/questions/3870064/performance-considerations-for-keyset-and-entryset-of-map

 

그래서 entrySet 을 이용해서 풀이도 해봤다.

import java.util.*;
//import java.util.Map.Entry;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        String answer = "";
        HashMap<String, Integer> map = new HashMap<>();
        
        for(String name : participant){
            map.put(name, map.getOrDefault(name, 0) + 1);
        }
        for(String name : completion){
            map.put(name, map.get(name)-1 );
        }
      
		// import의 주석부분을 해제하면 아래 Map.Entry를 그냥 Entry로 써도 오류 안남 (프로그래머스 기준)      
        for(Map.Entry<String, Integer> entry : map.entrySet()){
            if(entry.getValue() != 0) {
                answer = entry.getKey();
                break;
            }
        }
       
        return answer;
    }
}

 

 

• 학습할 것

- HashMap과 HashSet

- getOrDefault()

- Map의 keySet()과 entrySet()