UNIST, CSE 3th

2 minute read

149. Max Points on a Line (hard)

생각보다 쉽게 풀려서 깜짝 놀랐다. 생각한대로 구현하니까 바로 풀림;

class Solution:

    def acc(self, point1, point2):
        if point1[0] == point2[0]:
            return math.inf
        return (point2[1] - point1[1]) / (point2[0] - point1[0])

    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        res = 0
        for i in range(n):
            arr = {}
            for j in range(i + 1, n):
                acc = self.acc(points[i], points[j])
                arr[acc] = arr.get(acc, 0) + 1
            max_value = 0
            for value in arr.values():
                if value > max_value:
                    max_value = value
            res = max(res, max_value + 1)
        return res

934. Shortest Bridge (medium, re-try)

저번과 다르게 구현방식을 바꾸어봤다. 저번에는 어떻게든 recursive하게 shortest bridge를 찾으려고 했었는데, 그렇게 구현하는게 너무 비효율적이고 복잡한 것 같아서 spread 함수를 수정하여 모든 island의 포인트를 배열형식으로 반환하게 만들고 뽑아낸 island의 각 포인트들의 distance를 계산하여 가장짧은 다리의 길이를 찾는 방식으로 구현하였다.

그러나, 늘 그렇듯이 time exceedeed 가 떠버리고 말았다. 그렇다면 더 효율적인 방버이 있다는 얘기인데, 다시한번 고민해보기로 했다.

# stuck at 91/97 test cases
class Solution:

    def spread(self, grid, x, y, arr, block):
        n = len(grid)
        if x < 0 or x >= n or y < 0 or y >= n:
            return
        if grid[x][y] != 1:
            return
        grid[x][y] = block
        arr.append([x, y])
        self.spread(grid, x + 1, y, arr, block)
        self.spread(grid, x - 1, y, arr, block)
        self.spread(grid, x, y + 1, arr, block)
        self.spread(grid, x, y - 1, arr, block)

    def distance(self, point1, point2):
        return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])
        
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        island1, island2 = [], []
        count = 0
        for x in range(n):
            for y in range(n):
                if grid[x][y] == 1:
                    if count == 0:
                        self.spread(grid, x, y, island1, 2)
                        count += 1
                    else:
                        self.spread(grid, x, y, island2, 3)
                    
        # print(grid)
        res = 10**9
        for point1 in island1:
            for point2 in island2:
                res = min(res, self.distance(point1, point2))
        return res - 1

찾아낸 Solution

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q, head = [], -1
        dis = []
        visited = [[False] * n for _ in range(n)]
        
        # 첫번째 island의 블럭을 찾아서 q에 추가.
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    q = [[i, j]]
                    visited[i][j] = True
                    dis.append(0)
                    break
            if len(q) > 0:
                break
        
        # 첫번째 island의 전체를 추가하는 부분
        # q와 dis가 1대 1 대응.
        # q[index] -> point
        # dis[index] -> shortest length
        # 같은 형식으로 구현하는 것 같음.
        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        while head < len(q) - 1:
            head += 1
            x, y = q[head][0], q[head][1]
            for d in dirs:
                xx, yy = x + d[0], y + d[1]
                if xx < 0 or xx >= n or yy < 0 or yy >= n:
                    continue
                if visited[xx][yy] or grid[xx][yy] == 0:
                    continue
                q.append([xx, yy])
                visited[xx][yy] = True
                dis.append(0)
                
        # 가장 중요한 부분인데, ripple 처럼 퍼져나가면서 distance를 계산하는 방식
        # 이전에는 dis에 island만 값이 저장되어있었다면, 이제는 island가 아닌 부분까지 확장하여 사용
        # 신기한 접근방식?
        head = -1
        while head < len(q) - 1:
            head += 1
            x, y = q[head][0], q[head][1]
            for d in dirs:
                xx, yy = x + d[0], y + d[1]
                if xx < 0 or xx >= n or yy < 0 or yy >= n or visited[xx][yy]:
                    continue
                q.append([xx, yy])
                visited[xx][yy] = True
                dis.append(dis[head] + 1)
                if grid[xx][yy] == 1:
                    return dis[-1] - 1
        return 0

You may also enjoy