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

문제 링크

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

코딩테스트 연습 - 공 이동 시뮬레이션

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 queries에 대해 마지막부터 거꾸로 탐색을 진행
2. 현재 주어진 최종 점을 구간으로 확장하여 (최소행, 최대행, 최소열, 최대열) 쿼리의 반대 방향으로 점을 이동
   1. 구간이 확장될 가능성이 쿼리인 경우 구간을 확장 (이동 방향과 이 때 구간이 격자의 끝까지 이동한 경우)
   2. 구간이 단순하게 정확한 이동을 받은 쿼리인 경우 구간을 이동 (이 경우 불가능한 이동이 생길 수 있으며 답을 0 반환)

 이 문제의 경우 최종적으로 주어진 위치에 갈 수 있는 점들의 개수를 구해야 하지만, 만약 격자 속 모든 지점에 대해 쿼리를 따라가며 진행을 하는 경우 시간이 매우 오래 걸릴 수 있다. 이에 주어진 방법은 쿼리를 역순으로 탐색을 하며, 해당 쿼리를 만족할 수 있는 구간을 찾아나가는 것이다.

 다만 현재 문제 상에서 주의해야 할 점은, 만약 격자 이상으로 쿼리가 주어진 경우에는 해당 점이 격자의 끝에서 멈춘다는 것이다. 이를 역순으로 탐색을 할 때는, 가능한 구간의 확장으로 탐색을 진행해야 한다.

#

 예를 들어 현 위치의 점(혹은 구간)이 이 위치고 이전에 받은 쿼리가 좌측으로 2 이동이었다면, 이를 만족할 수 있는 구간은

#	#	#

 해당 구간이 되는 방식이다. 다만 주의해야 할 점이 만약 첫 구간이 좌측의 끝이 아닌 지점이었다면,

	#

 쿼리가 좌측 2 이동인 경우 결과가 구간의 확장이 아닌 정확한 이동이어야만 한다.

			#

 이를 확장하여 구간에 적용하면 가능한 구간에 있어 쿼리의 이동 방향과 현재 가능한 구간이 해당 방향에 끝까지 가 있는 경우라면 구간의 확장이 이루어지는 것이고, 이런 경우가 아니라면 구간조차도 단순히 이동을 하는 것이다. 이 때 단순히 이동을 함에 있어 쿼리가 불가능한 쿼리라면, 답을 0을 반환하면 된다.

 

class Solution {
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long answer;
        boolean possible = true;
        int minR = x, maxR = x, minC = y, maxC = y;

        for (int i = queries.length - 1; i >= 0; i--) {
            int queryType = queries[i][0], moveCount = queries[i][1];

            if (queryType == 0) {//좌측 이동 쿼리
                if (minC == 0) {//현재 구간 가장자리 좌측이 격자의 좌측(0열)과 겹친 경우
                    maxC = Math.min(m - 1, maxC + moveCount);
                } else {
                    if (minC + moveCount >= m) {//수행 불가능한 쿼리
                        possible = false;
                        break;
                    } else {//단순 이동 (구간의 경우 격자 밖을 벗어나 구간의 축소가 이루어질 수 있음)
                        minC = minC + moveCount;
                        maxC = Math.min(m - 1, maxC + moveCount);
                    }
                }
            }else if (queryType == 1) {//우측 이동 쿼리
                if (maxC == m - 1) {//현재 구간 가장자리 우측이 격자의 우측(m-1열)과 겹친 경우
                    minC = Math.max(0, minC - moveCount);
                } else {
                    if (maxC - moveCount < 0) {//수행 불가능한 쿼리
                        possible = false;
                        break;
                    } else {//단순 이동 (구간의 경우 격자 밖을 벗어나 구간의 축소가 이루어질 수 있음)
                        maxC = maxC - moveCount;
                        minC = Math.max(0, minC - moveCount);
                    }
                }
            }else if (queryType == 2) {//상단 이동 쿼리
                if (minR == 0) {//현재 구간 가장자리 상단이 격자의 상단(0행)과 겹친 경우
                    maxR = Math.min(n - 1, maxR + moveCount);
                } else {
                    if (minR + moveCount >= n) {//수행 불가능한 쿼리
                        possible = false;
                        break;
                    } else {//단순 이동 (구간의 경우 격자 밖을 벗어나 구간의 축소가 이루어질 수 있음)
                        minR = minR + moveCount;
                        maxR = Math.min(n - 1, maxR + moveCount);
                    }
                }
            }else if (queryType == 3) {//하단 이동 쿼리
                if (maxR == n - 1) {//현재 구간 가장자리 하단이 격자의 하단(n-1열)과 겹친 경우
                    minR = Math.max(0, minR - moveCount);
                } else {
                    if (maxR - moveCount < 0) {//수행 불가능한 쿼리
                        possible = false;
                        break;
                    } else {//단순 이동 (구간의 경우 격자 밖을 벗어나 구간의 축소가 이루어질 수 있음)
                        maxR = maxR - moveCount;
                        minR = Math.max(0, minR - moveCount);
                    }
                }
            }
        }

        if (possible) { //쿼리로 가능한 구간이 존재하는 경우 -> 구간 속 점들의 개수 계산
            answer = (long) (maxR - minR + 1) * (long) (maxC - minC + 1);
        } else {
            answer = 0;
        }

        return answer;
    }
}

결과