문제 설명 및 제한사항
아이디어 및 해결 방법
코드
def move(start, ds, maxval):
curr = start
for d in ds:
curr = max(min(curr + d, maxval), 0)
return curr
def solution(n, m, x, y, queries):
r, c = x, y
# 좌우, 상하를 나누어 생각합니다.
# 좌우 이동 쿼리만 뽑아내고, 이동하는 칸 수를 저장해둡니다.
cqueries = [q for q in queries if q[0] == 0 or q[0] == 1]
dcs = [q[1] if q[0] == 1 else -q[1] for q in cqueries]
# 상하 이동 쿼리만 뽑아내고, 이동하는 칸 수를 저장해둡니다.
rqueries = [q for q in queries if q[0] == 2 or q[0] == 3]
drs = [q[1] if q[0] == 3 else -q[1] for q in rqueries]
# 쿼리대로 이동을 마쳤을 때 x가 되는 최소 시작 x좌표와 최대 시작 x좌표를
# 이분탐색으로 구합니다.
# 먼저 최소 r 좌표
left, right = 0, n-1
while left < right:
mid = (left+right)//2
final = move(mid, drs, n-1)
if final >= r:
right = mid
else:
left = mid + 1
minr = left
if move(minr, drs, n-1) != r:
minr += 1
# 최대 r 좌표
left, right = 0, n-1
while left < right:
mid = (left+right)//2
final = move(mid, drs, n-1)
if final > r:
right = mid
else:
left = mid + 1
maxr = left
if move(maxr, drs, n-1) != r:
maxr -= 1
# 최소 c 좌표
left, right = 0, m-1
while left < right:
mid = (left+right)//2
final = move(mid, dcs, m-1)
if final >= c:
right = mid
else:
left = mid + 1
minc = left
if move(minc, dcs, m-1) != c:
minc += 1
# 최대 c 좌표
left, right = 0, m-1
while left < right:
mid = (left+right)//2
final = move(mid, dcs, m-1)
if final > c:
right = mid
else:
left = mid + 1
maxc = left
if move(maxc, dcs, m-1) != c:
maxc -= 1
if minc > maxc or minr > maxr:
return 0
return (maxc - minc + 1) * (maxr - minr + 1)
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges