[코테연습] 2349. Design a Number Container System

https://leetcode.com/problems/design-a-number-container-system/description/?envType=daily-question&envId=2025-02-08

 

1. 문제타입

• 자료구조 문제: NumberContainers 시스템을 구현하는 문제로, 주어진 인덱스에 대해 숫자를 변경하고, 숫자에 해당하는 가장 작은 인덱스를 빠르게 찾는 기능을 구현해야 합니다.
• 맵과 세트를 활용한 문제: 숫자와 인덱스를 연결하는 맵과, 인덱스를 빠르게 찾을 수 있도록 하는 집합(Set)을 사용합니다.

2. 문제분석

• change(int index, int number):
  • 주어진 index에 해당하는 숫자를 number로 변경하는 작업입니다.
  • 기존 숫자에 해당하는 인덱스를 제거하고, 새로운 숫자에 해당하는 인덱스를 추가해야 합니다.
• find(int number):
  • 주어진 숫자에 대해 가장 작은 인덱스를 찾는 작업입니다.
  • 숫자에 해당하는 인덱스 목록을 저장하는 방식으로, 최소 인덱스를 빠르게 반환해야 합니다.

3. 문제풀이

• change 메서드:
  • 먼저 index에 기존 숫자가 있는지 확인합니다.
  • 기존 숫자가 있으면 saveIndex에서 해당 숫자의 인덱스를 제거하고, 숫자 목록을 업데이트합니다.
  • 새로운 숫자를 map에 저장하고, saveIndex에서 숫자에 해당하는 인덱스를 추가합니다.
  • saveIndex는 TreeSet을 사용하여, 숫자에 대한 인덱스를 자동으로 정렬합니다. 이로 인해 find에서 정렬을 다시 할 필요가 없게 됩니다.
• find 메서드:
  • 주어진 숫자에 해당하는 인덱스를 saveIndex에서 찾습니다.
  • TreeSet을 사용하므로, 인덱스는 자동으로 오름차순으로 정렬되어 있으며, 가장 작은 인덱스는 iterator().next()를 통해 바로 찾을 수 있습니다.

 

 

> java

import java.util.*;

class NumberContainers {

    // index -> number 매핑
    Map<Integer, Integer> map;
    // number -> Set of index 매핑
    Map<Integer, Set<Integer>> saveIndex;

    public NumberContainers() {
        map = new HashMap<>();
        saveIndex = new HashMap<>();
    }
    
    // 숫자 변경 메서드
    public void change(int index, int number) {
        int currentNumber = map.getOrDefault(index, -1);
        
        // 기존 숫자와 다를 경우에만 작업
        if (currentNumber != number) {
            if (currentNumber != -1) {
                // 기존 숫자의 인덱스를 saveIndex에서 제거
                Set<Integer> set = saveIndex.get(currentNumber);
                if (set != null) {
                    set.remove(index);
                    if (set.isEmpty()) {
                        saveIndex.remove(currentNumber);  // 더 이상 사용되지 않는 숫자는 제거
                    }
                }
            }
            
            // 새로운 숫자와 인덱스 업데이트
            map.put(index, number);
            saveIndex.computeIfAbsent(number, k -> new TreeSet<>()).add(index); // TreeSet을 사용하여 자동 정렬
        }
    }
    
    // 숫자에 대해 가장 작은 인덱스를 찾는 메서드
    public int find(int number) {
        Set<Integer> set = saveIndex.get(number);
        if (set == null || set.isEmpty()) {
            return -1;
        }
        // TreeSet이므로 자동으로 정렬된 상태에서 가장 작은 인덱스를 반환
        return set.iterator().next();
    }
}

/**
 * 사용 예:
 * NumberContainers obj = new NumberContainers();
 * obj.change(index, number);
 * int param_2 = obj.find(number);
 */