[LV.1][JAVA] 완주하지 못한 선수(feat. TreeMap)

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

프로그래머스

푸는 동안 사고과정 및 개선점

처음에는 진짜 두 배열을 정렬해서 비교하면 되겠지라고 생각했다. 근데 입력이 10만이라 아마 그렇게 했으면 효율성 검사에서 걸리지않았을까..
동명이인이 있는 상태라 Set은 못쓰고, 그래서 Map을 썼다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        TreeMap<String, Integer> tm = new TreeMap();
        for(String name: participant){
            tm.put(name, tm.getOrDefault(name, 0)+1);
        } // 트리맵에 저장해두기 -> 굳이 TreeMap일 필요없음
        // 이제 completion을 돌면서 처리하자
        for(String name: completion){
            tm.put(name, tm.get(name)-1);
        } // 0이면 완주했다는 의미가 될 것
        
        Iterator<String> keys = tm.keySet().iterator();
        while(keys.hasNext()){
            String key = keys.next();
            if(tm.get(key) != 0){
                answer = key;
                break;
            }
        }
        
        return answer;
    }
}

TreeMap을 쓰고, key를 이름, value를 인원수로 설정했다. 정렬이 필요없기때문에 HashMap을 쓰는 게 효율적이지만 그냥 숙련을 위해 TreeMap을 선택했다.

초기화할 때 getOrDefault를 쓴 이유는 value가 없을 때 null 반환하는 걸 막기 위함이다.

그렇게 다 처리를 하고 나서, 인원수가 1인 key를 찾아야 하는 게 문제였다. 위 코드처럼 keySet을 사용해도 되는데 이 경우 조회해야되는 값이 엄청 많다면 entrySet에 비해 엄청 느리다고 했다.

 

그리고 entrySet을 쓰면 iterator를 안써도 되기 때문에 아래처럼 해보는 건 어떨까

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        TreeMap<String, Integer> tm = new TreeMap();
        for(String name: participant){
            tm.put(name, tm.getOrDefault(name, 0)+1);
        } // 트리맵에 저장해두기 -> 굳이 TreeMap일 필요없음
        // 이제 completion을 돌면서 처리하자
        for(String name: completion){
            tm.put(name, tm.get(name)-1);
        } // 0이면 완주했다는 의미가 될 것
        
        for(Map.Entry<String, Integer> item : tm.entrySet()){
            if(item.getValue() != 0){
                answer = item.getKey();
                break;
            }
        }
        
        return answer;
    }
}

---

# 추가 공부

TreeMap 알아보기

// entrySet()을 사용하여 모든 항목 순회
for (Map.Entry<String, Integer> entry : tm.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + ": " + value);
}

// 특정 조건에 맞는 항목 찾기
for (Map.Entry<String, Integer> entry : tm.entrySet()) {
    if (entry.getValue() > 2) {
        System.out.println(entry.getKey());
    }
}

// 맵 수정하기
for (Map.Entry<String, Integer> entry : tm.entrySet()) {
    entry.setValue(entry.getValue() * 2);
}

Tree 시리즈 답게 레드블랙트리로 구현되어있고, SortedMap인터페이스의 구현체다.  키를 기준으로 정렬된 상태(기본은 오름차순)이며 entrySet을 사용하면 맵의 모든 key-value 쌍을 `Set<Map.Entry<K,V>>` 형태로 반환한다.

 

set이 add, remove였다면 map은 put, get, remove(key로 삭제, entrySet에서 삭제, key-value로 삭제)가 있다.

 

삭제만 좀 보면 아래와 같다.

// 1. 키를 사용한 삭제
tm.remove("Apple");

// 2. 키와 값을 모두 사용한 삭제
tm.remove("Banana", 2);

신기한 건 removeIf가 있는데 아래처럼 사용한다. 람다식을 쓰는건데 그냥 이런게 있다 정도만 기억하고 넘어가야 될 것 같다.

// 짝수만 제거하기
tm.entrySet().removeIf(entry -> entry.getValue() % 2 == 0);

 

putIfAbsent도 있어서 이걸 활용하면 value에 Collection도 넣을 수 있다.

tm.putIfAbsent("A", 1);

기존의 put이 무조건 키를 덮어썼다면 putIfAbsent는 키가 없을 때만 동작한다. 그래서 Collection같은 걸 new로 넣어줄 때 쓰면 되겠다.

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!