[프로그래머스 Level.3] 공 이동 시뮬레이션 (월간 코드 챌린지 시즌3) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 월간 코드 챌린지 시즌3 > 공 이동 시뮬레이션

 

 

 

문제 설명

 

 

n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.

 

• 열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
• 열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
• 행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
• 행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))

 

단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다. 예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때 query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다. (격자의 크기가 5행 × 4열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)

 

격자의 행의 개수 n, 열의 개수 m, 정수 x와 y, 그리고 쿼리들의 목록을 나타내는 2차원 정수 배열 queries가 매개변수로 주어집니다. n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 queries 내의 쿼리들을 순서대로 시뮬레이션했을 때, x행 y열에 도착하는 시작점의 개수를 return 하도록 solution 함수를 완성해주세요.

 

---

제한사항

• 1 ≤ n ≤ 109
• 1 ≤ m ≤ 109
• 0 ≤ x < n
• 0 ≤ y < m
• 1 ≤ queries의 행의 개수 ≤ 200,000
  • queries의 각 행은 [command,dx] 두 정수로 이루어져 있습니다.
  • 0 ≤ command ≤ 3
  • 1 ≤ dx ≤ 109
  • 이는 query(command, dx)를 의미합니다.

 

---

 

입출력 예

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

 

• 다음 애니메이션은 4개의 가능한 시작점에 대한 모든 시뮬레이션을 나타낸 것입니다.

 

 

• 어떤 곳에서 출발하더라도 항상 0행 0열에 도착하기 때문에, 4를 return 해야 합니다.

 

 

 

입출력 예 #2

 

• 다음 애니메이션은 10개의 가능한 시작점에 대한 모든 시뮬레이션을 나타낸 것입니다.

 

 

• 0행 1열, 1행 1열에서 출발했을 때만 0행 1열에 도착하므로, 2를 return 해야 합니다.

 

 

 

 

 

 

나의 코드

class Solution {
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long answer = -1;

        // 직사각형의 범위로 가능한 좌표 범위 조정 (x, y로 갈 수 있는 좌표의 범위는 직사각형 형태로 나온다)
        // 주어진 x, y는 x행 y열이므로 좌표로 변환 시 주의
        // 좌측 상단(x1, y1) 우측 상단(x2, y1)
        // 좌측 하단(x1, y2) 우측 하단(x2, y2)
        int x1 = y; int y1 = x;
        int x2 = y; int y2 = x;

        for(int i=queries.length-1; i>=0; i--) {
            // 열 감소
            if(queries[i][0] == 0) { 
                if(x1 != 0) x1 += queries[i][1]; // 좌측 좌표 열 감소 반대 방향으로 범위 늘림 

                if(m-1 < x1) return 0; // 좌측 좌표가 m-1 보다 커지면 범위가 좌표 밖이므로 가능한 답 없음
                
                x2 = (x2 + queries[i][1] < m) ? (x2 + queries[i][1]) : (m-1); // 우측 좌표 열 감소 반대 방향으로 범위 늘림 
            }
            
            // 열 증가
            if(queries[i][0] == 1) {
                if(x2 != m-1) x2 -= queries[i][1]; // 우측 좌표 열 증가 반대 방향으로 범위 늘림
                
                if(x2 < 0) return 0; // 우측 좌표가 0 보다 작아지면 범위가 좌표 밖이므로 가능한 답 없음

                x1 = (x1 - queries[i][1] >= 0) ? (x1 - queries[i][1]) : 0; // 좌측 좌표 열 증가 반대 방향으로 범위 늘림
            }
            
            // 행 감소
            if(queries[i][0] == 2) { 
                if(y1 != 0) y1 += queries[i][1]; // 상단 좌표 행 감소 반대 방향으로 범위 늘림
                
                if(n-1 < y1) return 0; // 상단 좌표가 n-1 커지면 범위가 좌표 밖이므로 가능한 답 없음

                y2 = (y2 + queries[i][1] < n) ? (y2 + queries[i][1]) : (n-1); // 하단 좌표 행 감소 반대 방향으로 범위 늘림
            }
            
            // 행 증가
            if(queries[i][0] == 3) { 
                if(y2 != n-1) y2 -= queries[i][1]; // 하단 좌표 행 증가 반대방향으로 범위 늘림
                
                if(y2 < 0) return 0; // 하단 좌표가 0 보다 작아지면 범위가 좌표 밖이므로 가능한 답 없음

                y1 = (y1 - queries[i][1] >= 0) ? (y1 - queries[i][1]) : 0; // 상단 좌표 행 감소 반대 방향으로 범위 늘림
            }
        }

        long X = x2 - x1 + 1;
        long Y = y2 - y1 + 1;

        answer = X * Y;

        return answer;
    }
}

 

풀이

1. 이 문제는 어떻게 풀어야 할지 감이 잘 잡히지 않아 다른 분의 설명을 참고하여 풀었다.
2. 공이 진행방향으로 벽에 붙어있다면 이동해야 할 때 벽에 막혀 제자리에 있게 된다. 따라서 좌표를 범위로 잡아 가능한 좌표의 범위를 움직여가며 구해야 한다.
3. 따라서 목표 좌표부터 시작해서 해당 명령의 반대 방향으로 이동 하며 가능한 좌표를 범위로 조정하면서 답을 구하도록 한다. (가능한 좌표의 범위는 직사각형 형태로 나온다)
4. 우선 도착 좌표[x][y]를 각각 x1, x2, y1, y2로 받는다. (주어진 x, y는 x행 y열이므로 반대로 받아 좌표로 판단한다.)
   좌측 상단(x1, y1)    우측 상단(x2, y1)
   좌측 하단(x1, y2)    우측 하단(x2, y2)
5. 이제 주어진 queries를 뒤에서 앞으로 순회하면서 명령과 반대방향으로 움직이며 범위를 구한다.
6. queries[i][0]이 0일 때는 열이 감소하므로 열이 증가하는 쪽으로 범위를 움직이고
   queries[i][0]이 1일 때는 열이 증가하므로 열이 감소하는 쪽으로 범위를 움직이고
   queries[i][0]이 2일 때는 행이 감소하므로 행이 증가하는 쪽으로 범위를 움직이고
   queries[i][0]이 3일 때는 행이 증가하므로 열이 감소하는 쪽으로 범위를 움직인다.
7. 중요한 점은 가직사각형을 그리는 가까운 좌표를 반대 방향으로 범위로 늘린 후에 해당 좌표가  좌표를 넘어가면 값이 존재하지 않기 때문에 0을 반환하도록 한다. (예를 들어 queries[i][0]이 0일 때 열이 감소하므로 열을 증가하는 쪽으로 범위를 늘리는데 x1이 맨 오른쪽 좌표(m-1)를 넘어가버리면 값이 존재하지 않기 때문에 0을 반환한다) 
8. 또한 직사각형을 그리는 먼 좌표가 좌표의 범위를 벗어나면 마지막 좌표로 다시 세팅을 해주어야 좌표의 범위 내에서 값을 구할 수 있다.  (예를 들어 queries[i][0]이 0일 때 열이 감소하므로 열을 증가하는 쪽으로 범위를 늘리는데 x2가 맨 오른쪽 좌표(m-1)를 넘어가버리면 m-1로 다시 세팅해주도록 한다)
9. 이렇게 queries를 뒤에서부터 순회하며 모든 명령을 반대 방향으로 수행한 후에 얻은 시작점으로 가능한 좌표들의 직사각형 범위이다. 따라서 좌측 상단(x1, y1), 우측 상단(x2, y1), 좌측 하단(x1, y2),우측 하단(x2, y2)의 좌표를 꼭지점으로 하는 직사각형의 범위가 시작점의 개수이므로 직사각형의 넓이를 구하면 (x2 - x1 + 1) * (y2 - y1 + 1) 가 된다.

 

 

참고 : https://school.programmers.co.kr/questions/29706