[백준] 문제 추천 시스템 version 1

시간복잡도 생각해보기

• N이 최대 10^5이므로 O(NlogN)에 해결 필요
• M은 최대 10^4이므로 O(N^2)까지 가능
• TreeSet, TreeMap을 사용해서 NlogN + 명령어를 수행하는 부분에서 (MlogN) 이므로 총 NlogN

풀이 아이디어

• 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다. -> 문제 번호가 난이도만 다른채 중복 가능하므로 Key는 안 되고 문제번호들을 Value로 두고 난이도를 TreeMap의 Key로 둬서 정렬해서 품.
• 한 난이도 당 여러 문제가 들어갈 수 있고, 명령어 수행 조건에 만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다, 만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다. 등의 조건이 있으므로 TreeSet을 Value로 둠. 
• TreeMap<Integer, TreeSet<Integer>> list = new TreeMap<>();
• TreeSet을 사용한 이유: 중복허용 X, 자동 정렬. 최솟값과 최댓값을 모두 얻을 수 있음. O(logN)에 삽입, 정렬, 제거 가능.
• 우선순위 큐 사용하지 않은 이유: 최솟값과 최댓값을 모두 얻기 어려움.

의사코드 / 풀이 과정

for (int i = 0; i < M; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    String console = st.nextToken();
    if (console.equals(add)) { //add 문제번호 문제난이도
        int solvedNumber = Integer.parseInt(st.nextToken());
        int level = Integer.parseInt(st.nextToken());
        list.putIfAbsent(level, new TreeSet<>());
        list.get(level).add(solvedNumber);
    } else if (console.equals(recommend)) {
        int level = Integer.parseInt(st.nextToken());
        if (level == 1) { //가장 어려운거
            int num = list.lastKey();
            sb.append(list.get(num).last()).append("\n");
        } else if (level == -1) {//가장 쉬운거
            int num = list.firstKey();
            sb.append(list.get(num).first()).append("\n");
        }
    } else if (console.equals(solved)) {
        int solvedNumber = Integer.parseInt(st.nextToken());
        list.entrySet().removeIf(entry -> {
            TreeSet<Integer> set = entry.getValue();
            if (set.contains(solvedNumber)) {
                if (set.size() == 1) {
                    return true;
                } else {
                    set.remove(solvedNumber);
                }
            }
            return false;
        });
    }
}

참고 자료

https://www.baeldung.com/java-hashmap-remove-entry

순회 중 컬렉션 값을 변경해야 할 때

• 키가 특정 값에 매핑된 경우에만 값을 삭제하려는 경우 사용한다.
• 이터레이터 중에 값을 제거하게 되면 순회가 망가질 수 있으므로 동기화 문제가 생길 수 있다. 스레드 안전 연산을 해야한다.
• 1. iterator 사용하기

  Iterator<Entry<Integer, TreeSet<Integer>>> iterator = list.entrySet().iterator();
  while (iterator.hasNext()) {
    Map.Entry<Integer, TreeSet<Integer>> entry = iterator.next();
    int level = entry.getKey();
    TreeSet<Integer> set = entry.getValue();
    if (set.size() == 1 && set.contains(solvedNumber)) {
        iterator.remove(); // 안전하게 level과 set 삭제
    } else {
        set.remove(solvedNumber);
    }
  }

  2. removeIf 사용(자바 8이상)Map의 메서드map.putIfAbsent(a,b) 는 키인 a가 이미 존재하면 b를 추가하는 것을 수행하지 않는다.2. getOrDefault(key,value)map.getOrDefault(key, 0) 은 key가 존재하면 해당 값을 반환하고, 존재하지 않으면 0을 반환한다.

  map.put(key, map.getOrDefault(key, 0) + 1);

  따라서 0에서 다시 +1을 해서 put을 하면 된다.
• 1. map.putIfAbsent(a,b)
• list.entrySet().removeIf(entry -> { TreeSet<Integer> set = entry.getValue(); if (set.contains(solvedNumber)) { if (set.size() == 1) { return true; } else { set.remove(solvedNumber); } } return false; }); }
• Iterator<Entry<String,String>> iterator = list.entrySet().iterator(); while(iterator.hasNext()){ if(iterator.next().getKey().equals("")) iterator.remove(); }