Leetcode Contest 290 - part1

contest 290

leetcode에서 처음 contest에 참가해보았습니다.

문제는 4문제가 나왔구요. 난이도는 Easy 1 , Medium 2, Hard 1 였습니다.

2248. Intersection of Multiple Arrays

🔎 문제설명

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums sorted in ascending order.

Example 1

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]

nums의 각 리스트마다 3,4가 포함되어서 [3,4]를 return합니다.

Example 2

Input: nums = [[1,2,3],[4,5,6]]
Output: []

각 리스트마다 중복되는 게 없기에 []를 return 합니다.

제한사항

• 1 ≤ nums.length ≤ 1000
• 1 ≤ sum(nums[i].length) ≤ 1000
• 1 ≤ nums[i][j] ≤ 1000
• All the values of nums[i] are unique.

---

🧊 파이썬 코드

일단 저의 접근 법은 숫자의 범위가 1부터 1000이기때문에 범위가 작다고 생각했습니다.

1-1000번 반복을 돌면서 각 리스트에 숫자를 포함하는지를 세면서 그 숫자가 모든 리스트에서 포함되면 res[]에 넣었습니다.

✏️ 제출한 코드

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        res =[]
        for i in range(1,1001):
            cnt = 0
            for l in nums:
                cnt += l.count(i)
                if cnt == len(nums):
                    res.append(i)
                    
        return res

539 ms 14.2 MB

⚒️ 끝나고 리팩토링

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        res =[]
        for i in range(1,1001):
            if all(i in l for l in nums):res.append(i)
                    
        return res

181 ms 14.1 MB

all()을 썻더니 확실히 빠르게 나왔습니다.

🍸 다른사람 코드

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        res = set()
        for lst in nums:
            if lst == nums[0]:
                res = set(lst)
            else:
                res &= set(lst)
        return sorted(list(res))

Runtime: 115 ms
Memory Usage: 14.1 MB

🍹 또다른사람 코드

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        return sorted(set.intersection(*[set(num) for num in nums]))

Runtime: 110 ms
Memory Usage: 14.3 MB

저는 set을 사용하지 않았지만 범위가 적은 것을 이용했기 때문에 제 코드도 나쁜풀이는 아니라고 생각합니다.

---

2249. Count Lattice Points Inside a Circle

🔎 문제설명

Given a 2D integer array circles where circles[i] = [xi, yi, ri] represents the center (xi, yi) and radius ri of the ith circle drawn on a grid, return the number of lattice points that are present inside at least one circle.

A lattice point is a point with integer coordinates.
Points that lie on the circumference of a circle are also considered to be inside it.

Example 1

Input: circles = [[2,2,1]]
Output: 5

원 안에 존재하는 녹색점 좌표의 갯수를 반환하면 되는 문제입니다.

Example 2

Input: circles = [[2,2,2],[3,4,1]]
Output: 16

원이 여러개 겹쳤을 땐, 중복되는 좌표는 하나씩만 카운트합니다.

제한사항

• 1 ≤ circles.length ≤ 200
• circles[i].length == 3
• 1 ≤ xi, yi ≤ 100
• 1 ≤ ri ≤ min(xi, yi)

---

🧊 파이썬 코드

먼저, 중복되는 좌표를 없애기 위해서 set()을 사용했습니다.

원 중심부터 반지름반경 모든 좌표를 점과점사이 공식을 통해서 포함여부를 따져서 풀었습니다.

✏️ 제출한 코드

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        res = set([])
        for x,y,r in circles: # circles.length <= 200
            sx = x-r
            sy = y-r
            for sx in range(x+r+1): 
                for sy in range(y+r+1):
                    if math.pow(r,2) >= math.pow(x-sx,2) + math.pow(y-sy,2):
                        res.add((sx,sy))
                     
        return len(res)

Runtime: 7245 ms
Memory Usage: 18.7 MB

성공하긴 했지만 결과를 보니, 코드가 쓰레기군요..🧹

🍷 다른사람 풀이

저는 바보였습니다. 4분의 1만 탐색하면 되는 거였군요..

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        ans = set()
        for x,y,r in circles:
            for dx in range(r+1):
                y_upper = int((r**2-dx**2)**0.5)
                for dy in range(y_upper+1):
                    ans.add((x+dx,y+dy))
                    ans.add((x+dx,y-dy))
                    ans.add((x-dx,y+dy))
                    ans.add((x-dx,y-dy))
        return len(ans)

또한 빨간점은 탐색하지 않게 y_upper를 구해줍니다.

Runtime: 1385 ms
Memory Usage: 18.8 MB

🍺 또다른사람 풀이

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        intervals = [[] for _ in range(201)]
        for x, y, r in circles:
            for i in range(-r, r + 1):
                d = math.floor(math.sqrt(r**2 - i**2))
				# Add [start, 0] and [end, 1] to the list of intervals.
                intervals[x + i].append([y - d, 0])
                intervals[x + i].append([y + d, 1])
        res = 0

        for l in intervals:
            if l:
                l.sort()
				# count of open intervals.
                count = 0
                for i, ind in l:
                    if count == 0:
                        s = i
                    if ind == 0:
                        count += 1
                    else:
                        count -= 1
                        if count == 0:
                            res += i - s + 1
        return res

Runtime: 182 ms
Memory Usage: 20.9 MB

이건 속도가 넘사네요..