[프로그래머스] 공 이동 시뮬레이션

문제 설명

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

제한사항

• 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 ≤ 10^9
  • 이는 query(command, dx)를 의미합니다.

---

풀이

실패
제한사항으로 보아 그냥 구현하는 것은 아니라는 것을 알 수 있었다. 그러다가 이동 방향의 반대로 가면서 이동 경로를 나타내는 직사각형의 넓이를 구한다는 아이디어까지는 떠올릴 수 있었다. 내가 놓쳤던 부분은

1. 방향만 반대로 갈 것이 아니라, 쿼리 순회 순서도 반대로 가야한다….
2. 반대로 이동할 때는, 이동 방향 반대편 경계선을 주의해야한다

2번 항목을 자세히 살펴보자면,

[1, 0, 0]   [1, 1, 0]
[1, 0, 0]   [1, 1, 0]
[0, 0, 0]   [0, 0, 0]

왼쪽 상태에서 입력 커맨드가 [왼쪽,1칸]이라고 할 떄, 반대 방향인 오른쪽으로 1칸 좌표를 옮기게 된다. 그런데 왼쪽 경계선이 0이므로, 경계선을 한칸 옮기는 것이 아니라 그대로 두어야한다. 처음에 떠올린 방법은 이동 방향으로 움직이다가 경계를 넘으면 반대 방향의 경계를 그만큼 늘려주는 것이었기 때문에 이 부분이 헷갈렸었다. 또 인지하지 못한 케이스는,

[0, 1, 0]     [0, 0, 0] 1
[0, 0, 0]     [0, 0, 0]
[0, 0, 0]     [0, 0, 0]

왼쪽 상태에서 입력 커맨드가 [왼쪽,2칸]이라고 할 떄, 반대 방향인 오른쪽으로 2칸 좌표를 옮기게 된다. 그런데 경계선(m=3)을 넘은 인덱스이므로, 외부에서 격자로 접근한 꼴이 된다. 순서대로 생각한다면 쉽게 떠올릴 수 있는데, 역순으로 생각하다보니 놓친 부분이었다.

코드

// 02:10 ~ 
#include <string>
#include <vector>
#include <iostream>

using namespace std;

long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
    long long answer = -1;
    int d, step;
    int x1 = x, x2 = x;
    int y1 = y, y2 = y;
    //  {x1,y1}
    //         {x2,y2} 
    for(int ri = queries.size() - 1; ri >= 0; --ri){
        d = queries[ri][0];
        step = queries[ri][1];
        // 좌우상하 -> 우좌하상
        if(d == 0){
            if(y1 != 0) y1 += step;
            y2 += step;
            if(y2 >= m) y2 = m - 1;
        } else if(d == 1){
            if(y2 != m - 1) y2 -= step;
            y1 -= step;
            if(y1 < 0) y1 = 0;
        } else if(d == 2){
            if(x1 != 0) x1 += step;
            x2 += step;
            if(x2 >= n) x2 = n - 1;
        } else if(d == 3){
            if(x2 != n - 1) x2 -= step;
            x1 -= step;
            if(x1 < 0) x1 = 0;
        }
        if(x1 >= n || x2 < 0 || y1 >= m || y2 < 0) return 0;
    }
    long long x_len = x2 - x1 + 1;
    long long y_len = y2 - y1 + 1;
    return x_len * y_len;
}