[ 99클럽/챌린저 ] 12일차 TIL : 공 이동 시뮬레이션

NaHyun_kkiimm·2024년 4월 12일

99일지 99클럽 Java TIL 개발자스터디 알고리즘 코딩테스트 프로그래머스 항해

99클럽

목록 보기

13/13

문제 요약

n*m 크기의 격자의 행에는 0 ~ n-1번의 번호가, 열에는 0 ~ m-1번의 번호가 채워져있다.
만약, 모든 칸에 한 개의 공을 둘 경우, queries 배열에 입력된 커맨드에 따라 공이 이동하여 목적지 칸 x, y로 도착하는 공은 총 몇 개인가?

[ 예시 ]

n	m	x	y	queries	result
2	2	0	0	[[2,1],[0,1],[1,1],[0,1],[2,1]]	4
2	5	0	1	[[3,1],[2,2],[1,1],[2,3],[0,1],[2,1]]	2

[ 제약 조건 ]

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)를 의미합니다.

[ 프로그래머스 ]

Java
출처) https://school.programmers.co.kr/learn/courses/30/lessons/87391

풀이

그리드 알고리즘 사용
보면 알겠지만, n과 m 그리고 dx의 범위가 $10^9$ 이다. 때문에, 모든 공들에게 커맨드를 내려 돌리는 완전탐색이나 Brute Force를 할 경우, 시간 초과가 날 것이다.
도착점에서 각 커맨드의 역순으로 동작시켜, 거꾸로 계산을 시작해보자. 이럴 경우, 모든 공들을 계산할 필요 없이, 해당 도착점으로 오는 공들의 개수를 쉽게 구할 수 있을 것이다.

(1) 규칙에 맞게 커맨드를 역으로 설정하자

0 : 오른쪽으로 이동 (y 증가)
1 : 왼쪽으로 이동 (y 감소)
2 : 아래로 이동 (x 증가)
3 : 위로 이동 (x 감소)

(2) 이동 진행

각 구간이 좌표가 격자의 가장자리 값이 아니라면, 이동만 수행한다.
- xMax >= n, yMax >= m일 경우, 이 끝부분임으로 이동조차 진행하지 않는다.
- xMin != 0, yMin != 0일 경우, 이동을 진행시킨다.
가장자리 값이라면, 부딪힘으로 인해 통합이 일어난 것이기에 확장을 진행한다.
- xMin == 0, yMin == 0 확장

(3) 공 개수 구하기

사각형 형태로 확장 및 겹침(축소)가 이뤄지기에 위에서 구한 4개의 값을 이용하여 사각형의 넓이를 구하면, 해당 값이 곧 목적지까지 도착할 수 있는 공의 개수가 된다.

※ 크게 와닿지 않다며, 링크의 시뮬레이션을 확인해보자

Code

/*
    도착점(x,y)에 대하여 각 쿼리를 반대로 돌려 동작시켜보자
    - 0 : 오른쪽으로 이동 (y 증가)
    - 1 : 왼쪽으로 이동 (y 감소)
    - 2 : 아래로 이동 (x 증가)
    - 3 : 위로 이동 (x 감소)
*/
class Solution {
    public long solution(int n, int m, long x, long y, int[][] queries) {
        long answer = 0;
        long xMax = x;
        long xMin = x;
        long yMax = y;
        long yMin = y;
        // (xMin, yMin) : 시작점이 될 수 있는 범위의 시작 부분
        // (xMax, yMax) : 시작점이 될 수 있는 범위의 끝 부분
        for(int i = queries.length-1; i >= 0; i--) {
            long weight = queries[i][1];
            switch (queries[i][0]) {
                // 왼쪽 이동 => 오른쪽 이동으로 변경
                case 0:
                    yMax += weight;
                    if (yMax >= m) yMax = m-1;
                    if (yMin != 0) yMin += weight;
                    break;
                // 오른쪽 이동 => 왼쪽 이동으로 변경
                case 1:
                    yMin -= weight;
                    if (yMin < 0) yMin = 0;
                    if (yMax != m-1) yMax -= weight;
                    break;
                // 위 이동 => 아래 이동으로 변경
                case 2:
                    xMax += weight;
                    if (xMax >= n) xMax = n-1;
                    if (xMin != 0) xMin += weight;
                    break;
                // 아래 이동 => 위 이동으로 변경
                case 3:
                    xMin -= weight;
                    if (xMin < 0) xMin = 0;
                    if (xMax != n-1) xMax -= weight;
                    break;
            }
            System.out.println(xMin + " " + yMin);
            System.out.println(xMax + " " + yMax + "\n");
            if (yMin >= m || yMax < 0 || xMin >=n || xMax < 0) return 0; 
        }
        answer = (xMax - xMin +1) * (yMax - yMin + 1);
        return answer;
    }
}