[Programmers] 공 이동 시뮬레이션 (Java)

1.  문제 링크

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

2.  문제

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 함수를 완성해주세요.

3.  제한사항

• 1 ≤ n ≤ $10^9$
• 1 ≤ m ≤ $10^9$
• 0 ≤ x < n
• 0 ≤ y < m
• 1 ≤ queries의 행의 개수 ≤ 200,000
  • queries의 각 행은 [command,dx] 두 정수로 이루어져 있습니다.
  • 0 ≤ command ≤ 3
  • 1 ≤ dx ≤ 109
  • 이는 query(command, dx)를 의미합니다.

입출력 예

4.  소스코드

class Solution {
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long lx = x, hx = x, ly = y, hy = y;

        for(int idx = queries.length - 1; idx >= 0; idx--) {
            int dir = queries[idx][0], amount = queries[idx][1];

            if(dir == 0) {
                if(ly != 0) ly += amount;
                hy = Math.min(m - 1, hy + amount);
            } else if(dir == 1) {
                if(hy != m - 1) hy -= amount;
                ly = Math.max(0, ly - amount);
            } else if(dir == 2) {
                if(lx != 0) lx += amount;
                hx = Math.min(n - 1, hx + amount);
            } else {
                if(hx != n - 1) hx -= amount;
                lx = Math.max(0, lx - amount);
            }

            if(hx < 0 || lx >= n || hy < 0 || ly >= m) return 0;
        }

        return (hx - lx + 1) * (hy - ly + 1);
    }
}

5.  접근

• (x, y)에서 시작하여 주어진 쿼리들을 역으로 수행하면서 (lx, ly), (hx, hy)라는 두 좌표를 통하여 시작점이 될 수 있는 좌표들의 범위를 찾습니다.
  • (lx, ly)는 시작점이 될 수 있는 가장 왼쪽 위의 좌표를 의미하고, (hx, hy)는 시작점이 될 수 있는 가장 오른쪽 아래의 좌표를 의미합니다.
  • 이 때, 도착점에서 역으로 쿼리를 수행하므로 이동 방향은 주어진 쿼리의 반대 방향이 될 것입니다.
• 이 문제에는 쿼리를 진행할 때 목적지가 격자 바깥인 경우 공은 더 이상 이동하지 않고 멈춘다는 조건이 존재합니다.
  • 그러므로 쿼리를 역순으로 진행하면서 아래와 같은 조건을 확인해야 합니다.
    • 쿼리의 방향이 0일 때, ly가 0인지 확인합니다.
      • 만약 0이라면 열이 1 이상 감소하여 0에 도달할 수 있는 위치들의 최소값은 0이기 때문에 ly는 변경되지 않습니다.
      • 0이 아니라면 목적지가 격자 바깥인 경우는 포함되지 않기 때문에 ly에 dx를 더해줍니다.
    • 쿼리의 방향이 1일 때, hy가 m - 1인지 확인합니다.
      • 만약 m - 1이라면 열이 1 이상 증가하여 m - 1에 도달할 수 있는 위치들의 최댓값은 m - 1이기 때문에 hy는 변경되지 않습니다.
      • m - 1이 아니라면 목적지가 격자 바깥인 경우는 포함되지 않기 때문에 hy에 dx를 빼줍니다.
    • 쿼리의 방향이 2일 때, lx가 0인지 확인합니다.
      • 만약 0이라면 행이 1 이상 감소하여 0에 도달할 수 있는 위치들의 최소값은 0이기 때문에 lx는 변경되지 않습니다.
      • 0이 아니라면 목적지가 격자 바깥인 경우는 포함되지 않기 때문에 lx에 dx를 더해줍니다.
    • 쿼리의 방향이 3일 때, hx가 n - 1인지 확인합니다.
      • 만약 n - 1이라면 행이 1 이상 증가하여 n - 1에 도달할 수 있는 위치들의 최댓값은 n - 1이기 때문에 hx는 변경되지 않습니다.
      • n - 1이 아니라면 목적지가 격자 바깥인 경우는 포함되지 않기 때문에 hx에 dx를 빼줍니다.