99클럽 코테 스터디 27일차 TIL + 공 이동 시물레이션

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

• 프로그래머스 - 공 이동 시뮬레이션 (문제 링크)
• 시뮬레이션
• 역순 접근

 

---

 

문제 설명

주어진 문제는 n x m 크기의 격자에서 공을 움직이는 쿼리들을 처리하여 특정 위치에 도달할 수 있는 시작점의 개수를 구하는 것입니다. 공은 4가지 방향으로 움직일 수 있으며, 주어진 쿼리에 따라 위치를 이동합니다. 이동 과정에서 공은 격자 밖으로 나갈 수 없으며, 벽에 부딪히면 그 위치에서 멈춥니다.

제한사항

• 격자의 크기 n과 m은 최대 10억까지 가능합니다.
• 주어지는 쿼리의 개수는 최대 200,000개입니다.
• 쿼리는 크게 4가지 방향으로 나눠져 있으며, 각각 행/열을 이동시킵니다.

입출력 예

예제 1

n = 2, m = 2, x = 0, y = 0
queries = [[2,1],[0,1],[1,1],[0,1],[2,1]]
Output: 4

예제 2

n = 2, m = 5, x = 0, y = 1
queries = [[3,1],[2,2],[1,1],[2,3],[0,1],[2,1]]
Output: 2

 

---

 

문제 접근

이 문제의 핵심은 공을 역순으로 시뮬레이션하는 것입니다. 공이 x, y 위치에 도달할 수 있는 시작점의 개수를 계산하기 위해, 주어진 쿼리들을 역순으로 실행하면서 가능한 시작점의 범위를 좁혀 나갑니다.

1. 역순 시뮬레이션
   • 쿼리를 역순으로 처리하며 가능한 행과 열의 범위를 좁혀나갑니다. 이는 공이 특정 위치에 도달할 수 있는 시작점의 범위를 찾기 위함입니다.
2. 범위 유효성 검사
   • 각 쿼리를 처리하면서 시작점의 범위가 유효한지 확인하고, 더 이상 유효하지 않은 경우 즉시 0을 반환합니다.
3. 가능한 시작점의 개수 계산
   • 역순으로 쿼리를 모두 처리한 후, 가능한 시작점의 개수를 계산하여 결과를 반환합니다.

 

풀이 - Java 코드

class Solution {

    public long solution(int n, int m, int x, int y, int[][] queries) {
        long startRow = x, endRow = x;
        long startCol = y, endCol = y;

        // 쿼리를 역순으로 실행
        for (int i = queries.length - 1; i >= 0; i--) {
            int direction = queries[i][0];
            int range = queries[i][1];

            switch (direction) {
                case 0: // 왼쪽으로 이동
                    if (startCol != 0) startCol += range;
                    endCol = Math.min(m - 1, endCol + range);
                    break;
                case 1: // 오른쪽으로 이동
                    if (endCol != m - 1) endCol -= range;
                    startCol = Math.max(0, startCol - range);
                    break;
                case 2: // 위쪽으로 이동
                    if (startRow != 0) startRow += range;
                    endRow = Math.min(n - 1, endRow + range);
                    break;
                case 3: // 아래쪽으로 이동
                    if (endRow != n - 1) endRow -= range;
                    startRow = Math.max(0, startRow - range);
                    break;
            }

            // 유효한 범위가 없어지면 바로 종료
            if (startRow > endRow || startCol > endCol) {
                return 0;
            }
        }

        // 가능한 시작점의 개수 계산
        return (endRow - startRow + 1) * (endCol - startCol + 1);
    }
}

풀이 설명

1. 역순 시뮬레이션
   • 쿼리를 역순으로 처리하면서 공이 시작할 수 있는 가능한 범위를 좁혀나갑니다. 각 쿼리마다 이동한 거리에 따라 시작점과 끝점을 조정합니다.
2. 범위 유효성 검사
   • 범위를 조정한 후, 시작점이 끝점을 넘어서는 경우 더 이상 유효한 시작점이 없으므로 0을 반환합니다.
3. 결과 계산
   • 최종적으로 남은 시작점의 범위 내의 모든 위치에서 공이 출발할 수 있으므로, 가능한 시작점의 개수를 계산하여 반환합니다.

 

---

 

마무리하며

• 쿼리를 역순으로 처리하여 결과를 유도하는 방법을 학습할 수 있었습니다.