title: "[프로그래머스] 공 이동 시뮬레이션 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/87391"
description: "프로그래머스 Level 3 문제 [공 이동 시뮬레이션]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

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)

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges