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

 

난이도: 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.

 

문제 예제

---

Example 1:

Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
Output: [1,2,2,3]
Explanation:


- After query 0, ball 1 has color 4.
- After query 1, ball 1 has color 4, and ball 2 has color 5.
- After query 2, ball 1 has color 3, and ball 2 has color 5.
- After query 3, ball 1 has color 3, ball 2 has color 5, and ball 3 has color 4.

 

Example 2:

Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
Output: [1,2,2,3,4]
Explanation:


- After query 0, ball 0 has color 1.
- After query 1, ball 0 has color 1, and ball 1 has color 2.
- After query 2, ball 0 has color 1, and balls 1 and 2 have color 2.
- After query 3, ball 0 has color 1, balls 1 and 2 have color 2, and ball 3 has color 4.
- After query 4, ball 0 has color 1, balls 1 and 2 have color 2, ball 3 has color 4, and ball 4 has color 5.

 

제한 사항

---

• 1 <= limit <= 109
• 1 <= n == queries.length <= 105
• queries[i].length == 2
• 0 <= queries[i][0] <= limit
• 1 <= queries[i][1] <= 109

 

✏️ Solution(솔루션)

---

class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        balls = {}
        check_color = defaultdict(int)
        answer = []

        cnt = 0
        for query in queries:
            ball, color = query

            if ball in balls:
                check_color[balls[ball]] -= 1
                if check_color[balls[ball]] == 0:
                    del check_color[balls[ball]]

            check_color[color] += 1
            balls[ball] = color

            answer.append(len(check_color))

        return answer

 

각 ball에 대해 쿼리에 맞는 color를 적용해 나갔다.

 

이 때 check_color라는 dictionary를 만들어 color가 바뀌면 기존 color에 대해 -1을 해주고 새로운 color에 대해 +1 해주었다.

바뀌지 않고 새로운 color가 칠해졌으면 그냥 check_color[color]에 +1을 해주었다.

 

만약 기존 color에 대해 -1을 했는데 그 값이 0이 되었으면 현재 상태에서 이 color은 없는 것이기 때문에 del를 통해 딕셔너리에서 아예 삭제 시켜주었다.

 

그리고 answer에 check_color에 길이를 넣어주고 마지막에 answer를 return 하였다.

근데 뜬금없이 Memory Limit Exceed가 발생했다.

 

처음에 balls를 [i for i in range(limit)]으로 설정했는데 limit이 10**9까지 있어 그런가 하고 balls를 기본 딕셔너리로 변경해주었더니 정답을 맞을 수 있었다.

 

이럴거면 limit은 왜 주어지는거지...

---

문제: 3160. Find the Number of Distinct Colors Among the Balls

 

깃허브: github

algorithmPractice/LeetCode/3434-find-the-number-of-distinct-colors-among-the-balls at main · laewonJeong/algorithmPractice