99클럽 코테 스터디 27일차 TIL / [프로그래머스] 공 이동 시뮬레이션

오늘의 학습 키워드

---

시뮬레이션

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 공 이동 시뮬레이션
• 난이도: Lv3

풀이

---

class Solution {
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long top = x, bottom = x, left = y, right = y;

        // 역으로 탐색
        for (int i = queries.length - 1; i >= 0; i--) {
            int command = queries[i][0];
            int dx = queries[i][1];

            if (command == 0) { // 좌
                if (left != 0) {
                    left += dx;
                }

                right = Math.min(m - 1, right + dx); 
            } else if (command == 1) { // 우
                if (right != m - 1) {
                    right -= dx;
                }

                left = Math.max(0, left - dx);
            } else if (command == 2) { // 상
                if (top != 0) {
                    top += dx;
                }

                bottom = Math.min(n - 1, bottom + dx);
            } else { // 하
                if (bottom != n - 1) {
                    bottom -= dx;
                }

                top = Math.max(0, top - dx);
            }

						// 배열을 벗어난 경우 답을 도출할 수 없음
            if (left >= m || right < 0 || top >= n || bottom < 0) {
                return 0;
            }
        }

        return (right - left + 1) * (bottom - top + 1);
    }
}

접근

• 행, 열의 크기가 최대 10^9으로 매우 커서 문제에 정의된대로 시뮬레이션을 구현하는 것은 불가능합니다.
• 따라서 목적지 지점에서 역으로 쿼리를 수행하며 정답이 될 수 있는 범위를 구하는 방식으로 구현합니다.
  • 예를 들어, 왼쪽으로 한 칸 이동하는 쿼리를 역으로 수행한다면 현 위치 기준 오른쪽 좌표에서 출발해야합니다.
  • 배열의 왼쪽 끝 좌표에서 왼쪽으로 한 칸 이동하는 쿼리를 역으로 수행한다면 현 위치와 현 위치 기준 오른쪽 좌표 모두 정답 대상이 됩니다.
  • 이처럼 정답이 될 수 있는 범위는 사각형 형태로 늘어나게 되므로 정답 범위의 좌상단, 우하단 좌표를 구해 정답을 도출할 수 있습니다.
• 위 예시에서 알 수 있듯, 쿼리 이동 방향의 반대로 범위를 확장시키면 됩니다.

  if (command == 0) { // 좌
      if (left != 0) {
          left += dx;
      }
  
      right = Math.min(m - 1, right + dx); 
  }

• 주의할 점은 쿼리를 수행할 때마다 올바른 정답 범위를 가졌는지 체크해야 합니다. (예시로, (-99,0) 에서 출발해야만 하는 경우는 존재할 수 없기 때문입니다.)

  // 배열을 벗어난 경우 답을 도출할 수 없음
  if (left >= m || right < 0 || top >= n || bottom < 0) {
      return 0;
  }

소요 시간

2시간