[LeetCode] 3160. Find the Number of Distinct Colors Among the Balls

https://leetcode.com/problems/find-the-number-of-distinct-colors-among-the-balls/description/

leetcode - Find the Number of Distinct Colors Among the Balls

문제 유형: 해시

문제 난이도: Medium

 

문제

You are given an integer limit and a 2D array queries of size n x 2.

There are limit + 1 balls with distinct labels in the range [0, limit]. Initially, all balls are uncolored. For every query in queries that is of the form [x, y], you mark ball x with the color y. After each query, you need to find the number of distinct colors among the balls.

Return an array result of length n, where result[i] denotes the number of distinct colors after ith query.

Note that when answering a query, lack of a color will not be considered as a color.

 

정수 limit과 n x 2의 크기의 2D배열 queries를 받습니다.

limit+1개의 공이 있습니다.

[0, limit]까지의 라벨이 붙어있고, 처음에는 색깔이 없습니다.

각 쿼리 [x, y]에는 공 x를 y색으로 칠해야 합니다.

그리고 수행 후, 공들에게 적용된 색깔들의 개수를 구해야 합니다.

 

result[i]에 쿼리 결과를 저장해서 반환하시오. 무색은 색깔로 안칩니다.

 

풀이

limit과 쿼리에서의 색깔의 범위가 10^9까지이다.

크기가 너무 커서 vector로는 해결이 안 된다.

대신, unordered_map을 이용해서 희소한 정보들을 효율적으로 처리한다.

 

공이 어떤 색깔인지를 저장하는 해시맵 하나,

색깔번호별로 몇 개의 공을 칠했는지 저장하는 해시맵을 하나 만든다.

 

각 쿼리를 처리하면서, 먼저 기존 색깔을 지우는 의미로 기존 색깔이 칠하고 있는 개수를 줄이고, 0이 된다면 색깔의 종류수를 1 뺀다.

그 뒤, 새 색을 칠한다.

새로운 색깔이 칠하는 개수를 +1하는데, 없던 색깔을 칠한 거라면 색깔의 종류수를 1 누적한다.

색깔의 종류수를 배열에 append해준다.

 

 

코드

C++

class Solution {
public:
    vector<int> queryResults(int limit, vector<vector<int>>& queries) {
        unordered_map<int, int> colors;
        unordered_map<int, int> colorUsing;
        int res = 0;

        int n = queries.size();
        vector<int> ans(n);
        for(int i = 0; i < n; ++i) {
            int b = queries[i][0];
            int c = queries[i][1];
            if(colors[b] != 0) {
                if(--colorUsing[colors[b]] < 1) --res;
            }

            colors[b] = c;
            if(++colorUsing[c] == 1) ++res;

            ans[i] = res;
        }

        return ans;
    }
};

 

 

Go

func queryResults(limit int, queries [][]int) []int {
    ballColors := make(map[int]int)
    colorUsing := make(map[int]int)
    n := len(queries)
    ans := make([]int, n)
    res := 0

    for i, query := range queries {
        b := query[0]
        c := query[1]

        if prevColor, exists := ballColors[b]; exists {
            colorUsing[prevColor]--
            if colorUsing[prevColor] == 0 {
                res--
            }
        }

        ballColors[b] = c
        colorUsing[c]++
        if colorUsing[c] == 1 {
            res++
        }

        ans[i] = res
    }

    return ans
}