[프로그래머스 Level3] 공 이동 시뮬레이션 - 파이썬(Python) - 월간 코드 챌린지 시즌3

https://school.programmers.co.kr/learn/courses/30/lessons/87391

프로그래머스

문제 설명

n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1,...,n-1번의 번호, 그리고 각 열은 0, 1,...,m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.

• 열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
• 열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
• 행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
• 행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))

단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다. 예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때 query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다. (격자의 크기가 5행 × 4 열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)

격자의 행의 개수 n, 열의 개수 m, 정수 x와 y, 그리고 쿼리들의 목록을 나타내는 2차원 정수 배열 queries가 매개변수로 주어집니다. n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 queries 내의 쿼리들을 순서대로 시뮬레이션했을 때, x행 y열에 도착하는 시작점의 개수를 return 하도록 solution 함수를 완성해 주세요.

 

 

---

내용은 간단하지만 시간 초과를 조심해야 하는 문제이다.

문제의 예제들을 가만히 보니 한 쿼리마다 이동가능한 공들은 서로 흩어져 있는 것이 아닌, 직사각형 범위 내에서 범위가 계속해서 변화하는 것이 보였다. 이 특징을 이용하여 O(200,000)의 시간복잡도로 문제를 풀 수 있다.

 

또한, 최종 위치인 (x, y)에 가기까지 실행된 쿼리들을 거꾸로 올라가며 그 이전 위치를 추측하면서 진행해야 한다.

 

+ 테스트 33번과 34번을 통과하지 못한다면, 최종적으로 x행 y열에 도착하게 될 시작점의 개수가 0개라는 경우를 놓친 것이다.

 

 

예제 2번의 풀이 과정 (거꾸로 실행)

 

 

<< 최종 코드 >>  ※ x, y 위치를 바꾸어 사용함

def solution(n, m, y, x, queries):
    minYX, maxYX = [y, x], [y, x]
    while queries:
        direction, dx = queries.pop()
        if direction == 0:
            maxYX[1] = min(maxYX[1] + dx, m - 1)
            if minYX[1] != 0:
                minYX[1] = minYX[1] + dx
        elif direction == 1:
            minYX[1] = max(minYX[1] - dx, 0)
            if maxYX[1] != m - 1:
                maxYX[1] = maxYX[1] - dx
        elif direction == 2:
            maxYX[0] = min(maxYX[0] + dx, n - 1)
            if minYX[0] != 0:
                minYX[0] = minYX[0] + dx
        else:
            minYX[0] = max(minYX[0] - dx, 0)
            if maxYX[0] != n - 1:
                maxYX[0] = maxYX[0] - dx
        if minYX[0] >= n or maxYX[0] < 0 or minYX[1] >= m or maxYX[1] < 0:
            return 0
    return (maxYX[0] - minYX[0] + 1) * (maxYX[1] - minYX[1] + 1)

 

• query의 명령을 거꾸로 따라가며 그 이전 위치를 추측하기
• dx의 크기에 따른 좌표 위치 조정 과정이 조금 복잡하니 조심하기