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

문제 설명

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

문제 풀이

• 인사이트가 필요한 구현 문제였다.
• 우선 생각 해야할 것은 완전탐색(DFS, BFS)으로 좌표 1개 단위로 풀이를 진행하면 무조건 시간초과가 난다는 점이다.
  - 예를 들어 (x,y)=(0,0)이고 쿼리 마지막 2개가 (0, 10억), (3, 10억)이면 쿼리 역순으로 가능한 지점을 추적한다고할 때, 마지막 쿼리 2개 부터 10억x10억개의 가능한 좌표가 나오므로 시간초과가 발생한다.
• 좌표기준이 아닌 쿼리 역순으로 직사각형 형태의 x범위, y범위를 고려해야한다.
• 아래와 같은 로직을 통해 x, y범위를 쿼리 역순으로 추적해나간다.

  • x, y 범위를 sx, ex, sy, ey로 표현한다.
  • dir = 0, 1 인 경우 y좌표에 대해 고려, dir = 2, 3인 경우 x좌표에 대해 고려하는데 로직은 같으므로 다음 함수로 공통화 시킨다.
  • calNextRange(int s, int e, int move, int max)
  • 우선 특정 쿼리 역방향으로 이동했을 때 다음 s, e는 다음과 같다.
    - (s==0 && move > 0) 일 경우 : nextS = 0, 아닐 경우 : nextS = s + move
    - (e==max-1 && move < 0)일 경우 : nextE = max-1, 아닐 경우 : nextE = e + move
  • 이후 다음 범위 (nextS, nextE)에 대해 아래 케이스를 고려한다.
    1. nextS 범위 벗어남, nextE 범위 벗어남 -> 가능한 케이스 없음, 종료
    2. nextS 범위 벗어남, nextE 범위 내 -> (0, nextE) 리턴
    3. nextS 범위 내, nextE 범위 벗어남 -> (nextS, max-1) 리턴
    4. nextS 범위 내, nextE 범위 내 -> (nextS, nextE) 리턴

• 모든 쿼리(역순)에 대해 위 로직을 수행하고 나온 x범위, y범위를 곱해주면 결과 좌표수가 나온다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int[] dx = {0,0,1,-1};  //기존 방향의 역방향 고려 
    public int[] dy = {1,-1,0,0};  //기존 방향의 역방향 고려 

    public int[] calNextRange(int s, int e, int move, int max) {
        int nextS = (s==0 && move > 0) ? 0 : s + move;
        int nextE = (e==max-1 && move < 0 ) ? max-1 : e + move;
        //1 둘 다 범위 벗어남
        if ((nextS < 0 || nextS >= max) && (nextE < 0 || nextE >= max)) {
            return new int[]{-1, -1};
        }
        //2 시작점만 범위 벗어남
        if (nextS < 0 && nextE >= 0 && nextE < max) {
            return new int[]{0, nextE};
        }
        //3 종료점만 범위 벗어남
        if (nextE >= max && nextS >= 0 && nextS < max) {
            return new int[]{nextS, max-1};
        }
        //4 둘 다 범위 이내
        return new int[]{nextS, nextE};
    }

    public long solution(int n, int m, int x, int y, int[][] queries) {
        int sx, ex, sy, ey;
        sx = ex = x;
        sy = ey = y;
        for (int i = queries.length - 1; i >= 0; i--) {
            int dir = queries[i][0];
            int cnt = queries[i][1];

            //y 좌표 기준
            if (dir == 0 || dir == 1) {
                int[] res = calNextRange(sy, ey, cnt * dy[dir], m);
                if (res[0] == -1) return 0;
                sy = res[0]; ey = res[1];
            }
            //x 좌표 기준
            else {
                int[] res = calNextRange(sx, ex, cnt * dx[dir], n);
                if (res[0] == -1) return 0;
                sx = res[0]; ex = res[1];
            }
        }
        return (long)(ex - sx + 1) * (long)(ey - sy + 1);
    }
}