[코테연습] 3160. Find the Number of Distinct Colors Among the Balls

https://leetcode.com/problems/find-the-number-of-distinct-colors-among-the-balls/description/?envType=daily-question&envId=2025-02-07

 

문제타입

• 동적 배열 업데이트 문제
• 색깔 변경에 따른 상태 추적 문제
• 배열 내의 중복 처리 및 동적 집합 관리 문제

문제 분석

• 배경: 주어진 배열의 공들에 대해 색깔을 동적으로 변경하고, 각 변경 후에 배열에 존재하는 고유한 색깔의 개수를 구하는 문제입니다.
• 입력:
  • 공의 개수 n과 m개의 쿼리로 이루어진 queries가 주어짐
  • 각 쿼리는 공의 색을 변경하는 명령입니다. 각 쿼리에는 공의 인덱스와 새로운 색깔이 주어짐.
• 출력: 각 쿼리 후에 현재 공들에서 고유한 색깔의 개수를 구하여 출력합니다.
• 문제의 핵심:
  • 각 공의 색이 변경될 때마다 전체 색깔의 중복을 계산해야 하므로, 색깔을 추적하는 방법이 중요합니다.
  • 효율적으로 색깔의 개수를 업데이트해야 하므로 색깔을 동적으로 관리하는 자료구조가 필요합니다.

문제 풀이

1. 배열 사용:
   • balls[] 배열을 사용하여 각 공의 색깔을 기록합니다.
2. 동적 색깔 추적:
   • 색깔의 개수를 추적하기 위해 Map<Integer, Integer> col을 사용합니다. 이 맵은 각 색깔에 대한 공의 개수를 추적합니다.
   • 색깔이 변할 때마다 이전 색깔의 개수를 줄이고 새로운 색깔의 개수를 증가시킵니다.
3. 결과 계산:
   • col.size()를 사용하여 현재 활성화된 고유한 색깔의 개수를 구합니다. 이 값은 각 쿼리마다 갱신됩니다.

 

 

class Solution {
    public int[] queryResults(int limit, int[][] queries) {
        // bal: 각 공의 색을 추적하는 맵
        // col: 각 색깔의 공 개수를 추적하는 맵
        Map<Integer, Integer> bal = new HashMap<>();
        Map<Integer, Integer> col = new HashMap<>();
        
        // 결과 배열을 생성. queries.length만큼의 결과를 저장할 예정
        int n = queries.length;
        int[] res = new int[n];

        // 각 쿼리 처리
        for (int i = 0; i < n; i++) {
            // 쿼리에서 공의 인덱스(queries[i][0])와 색깔(queries[i][1])을 추출
            int idx = queries[i][0];
            int color = queries[i][1];

            // 해당 공에 색이 이미 배정된 경우와 아닌 경우 처리
            if (!bal.containsKey(idx)) {
                // 만약 공에 색이 배정된 적이 없다면 새로운 색을 배정
                bal.put(idx, color);
            } else {
                // 이미 배정된 색깔이 있다면 색을 변경하는 과정
                int oldColor = bal.get(idx); // 기존 색깔 가져오기
                
                // 기존 색깔의 개수를 갱신
                if (col.get(oldColor) == 1) {
                    // 기존 색깔의 공이 마지막 하나라면, 해당 색을 제거
                    col.remove(oldColor);
                } else {
                    // 그렇지 않으면 색깔 개수를 1 감소시킨다
                    col.put(oldColor, col.get(oldColor) - 1);
                }
                
                // 공의 색을 새로운 색으로 갱신
                bal.put(idx, color);
            }

            // 새로운 색깔의 공 개수를 갱신
            col.put(color, col.getOrDefault(color, 0) + 1);

            // 현재까지의 distinct 색깔의 수를 결과 배열에 저장
            res[i] = col.size();
        }

        // 최종 결과 배열 반환
        return res;
    }
}