문제 소개
N × N 크기의 격자가 있고, 각 셀 (x, y)에는 램프가 하나씩 놓여 있다고 가정해 봅시다. 처음에는 일부 램프만 켜져 있으며, lamps[i]는 켜져 있는 i번째 램프의 위치를 나타냅니다. 켜진 램프는 자신이 위치한 x축 방향, y축 방향, 그리고 두 대각선 방향의 모든 칸을 비춥니다.
이제 i번째 질의 queries[i] = (x, y)에 대해, 셀 (x, y)가 비춰지고 있다면 답은 1, 그렇지 않다면 0입니다. 또한 각 질의가 처리된 후에는 해당 셀 자신과 인접한 8방향 셀에 있는 램프를 모두 꺼야 합니다. 최종적으로 각 질의에 대한 답을 순서대로 담은 배열을 반환하면 됩니다.
예를 들어 N = 5이고 램프가 [[0,0],[4,4]]에 위치하며, 질의가 [[1,1],[1,0]]일 때 출력은 [1,0]이 됩니다.
해결 접근 방법
매 질의마다 전체 격자를 확인하는 것은 비효율적이므로, 해시맵(딕셔너리)을 활용해 행, 열, 두 대각선별로 켜진 램프 수를 관리하면 O(1) 시간에 조도 여부를 판별할 수 있습니다. 구체적인 단계는 다음과 같습니다 −
lamps := 주어진 lamps 배열로부터 만든 좌표 쌍의 집합(set)
x, y, diag1, diag2라는 네 개의 카운터 맵 생성
lamps의 각 좌표 쌍 (i, j)에 대해:
x[i] += 1, y[j] += 1 로 행·열 카운트 증가
diag1[i + j] += 1, diag2[i - j] += 1 로 양대각선 카운트 증가
ans := 빈 리스트
질의 목록 C의 각 값 i에 대해:
a := i[0], b := i[1]
x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 이면 1, 아니면 0을 ans에 추가
row를 a - 1부터 a + 1까지 반복:
col을 b - 1부터 b + 1까지 반복:
(row, col)이 lamps 집합에 있다면:
x[row] -= 1
y[col] -= 1
diag1[row + col] -= 1
diag2[row - col] -= 1
lamps에서 (row, col) 제거
ans 반환
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다 −
예제 코드
from collections import defaultdict
class Solution(object):
def gridIllumination(self, N, b, C):
lamps = {(i[0], i[1]) for i in b}
x, y, diag1, diag2 = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int)
for i, j in lamps:
x[i] += 1
y[j] += 1
diag1[i + j] += 1
diag2[i - j] += 1
ans = []
for i in C:
a = i[0]
b = i[1]
ans.append(1 if x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 else 0)
for row in range(a - 1, a + 2):
for col in range(b - 1, b + 2):
if (row, col) in lamps:
x[row] -= 1
y[col] -= 1
diag1[row + col] -= 1
diag2[row - col] -= 1
lamps.remove((row, col))
return ans
ob = Solution()
N = 5
lamps = [[0,0],[4,4]]
query = [[1,1],[1,0]]
print(ob.gridIllumination(N, lamps, query))입력
5, [[0,0],[4,4]], [[1,1],[1,0]]
출력
[1, 0]