문제출처: https://programmers.co.kr/learn/courses/30/lessons/87391#
코딩테스트 연습 - 공 이동 시뮬레이션
n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리
programmers.co.kr
문제이해
목표
n행 m열의 격자 안에서 주어진 쿼리를 실행했을 때 정해진 도착지점에 도착할 수 있는 시작점의 개수를 구해라.
도착지점
(x,y)
쿼리 규칙
열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))
단, 공은 격자 바깥으로 이동할 수 없으며 그자리에서 멈춤
중요 변수 정보
1 ≤ n ≤ 10^9
1 ≤ m ≤ 10^9
0 ≤ x < n
0 ≤ y < m
실패한 사례
- 모든 칸을 값 1을 가진 노드로 간주, 주어진 쿼리를 하나씩 모든 노드에 다 실행시켜봐서 이동을 하면 겹치는 노드가 발생한다. 이때, 윷놀이 말이 업는 것 처럼 겹치는 노드는 태워서 함께 움직이는 방식으로 생각 (값을 합침)
10억 x 10억 의 데이터 접근 => 메모리 초과
노드 하나하나에 접근하려 하면
메모리 초과 또는 시간 초과가 되는 것을 예상함 (10억 x 10억의 데이터)
따라서, 도착지점에서부터 거꾸로 탐색하는 방식으로 사고 전환
풀이
1. 쿼리를 반대방향으로 반대순서로 만든다.
2. 변경된 쿼리를 도착지점(x,y)을 출발점으로 생각하여 돌려보고 '기준점'을 찾는다.
3. 기준점 기준에서 제대로된 쿼리를 다시 실행했을때
- 만약 기준점에서 쿼리를 다시 실행했는데도 도착자리에 오지 못했다면, 그것은 해당 자리에 도착하는 것이 불가능한 경우이다. 이 경우 답이 0이다.
- 그 외에는 답이 존재한다.
답 COUNT 방법
- 어떤 지점에서 출발해서 정답으로 갈 수 있는 칸을 세기 위해(사각형의 넓이를 이용할 것이다)
up, down, left, right를 사용할 건데, 기준점으로 초기화 시켜준다.
- 만약 풀이3을 실행 중 위, 아래, 왼쪽, 오른쪽 벽에 부딪히는 경우 기준점부터 해당 부딪힌 벽까지의 칸들은 모두 쿼리를 실행했을 때 도착지에 도착할 수 있는 칸으로, 정답을 세는데 포함되어야 한다.
왜냐하면 해당 칸들도 똑같은 쿼리순서에 똑같은 벽에 밀려서 똑같은 도착지에 도착하기 때문이다. => 규칙을 찾음
- 따라서, 어떤 벽에 부딪혔을 때
위쪽벽은 up을 0으로, 아래쪽 벽은 down을 n-1로, 왼쪽벽은 left를 0으로, 오른쪽벽은 right를 m-1로 갱신시켜준다. 이때 정답은 answer = (long) (right - left + 1) * (down - up + 1);이 된다.
- 아무데도 부딪히지 않는다면 정답은 1개이다. 밀려서 동선이 겹쳐지는 노드가 없기 때문
그림설명
1. Reverse Queries 만들기
2. 도착지에서 Reverse Queries 실행, 기준점 구해짐
3. 기준점에서 제대로된 Queries 실행
4. 3번과정을 실행했을때, 닿은 윗벽과 오른쪽벽을 확인, up, right 값을 갱신시켜줌
5. 정답 도출
출제의도는 이렇게 푸는 방식이 아닐걸로 예상한다,,
나만의 규칙을 찾아서 문제를 풀었다. 공식적인 풀이가 올라오면 꼭 확인해보고 학습해야겠다.
소스코드
public class 월코챌3_공이동시뮬레이션 {
public long solution(int n, int m, int x, int y, int[][] queries) {
long answer = 0;
// 기준점
int newRow = x;
int newCol = y;
// 쿼리를 거꾸로, 기준점을 구한다.
for (int i = queries.length - 1; i >= 0; i--) {
int[] query = queries[i];
int dx = query[1]; // 몇 칸
// 이동
if (query[0] == 0) { // 왼쪽 -> 오른쪽
newCol += dx;
newCol = Math.min(m - 1, newCol);
} else if (query[0] == 1) { // 오른쪽 -> 왼쪽
newCol -= dx;
newCol = Math.max(0, newCol);
} else if (query[0] == 2) { // 위쪽 -> 아래쪽
newRow += dx;
newRow = Math.min(n - 1, newRow);
} else { // 아래쪽 -> 위쪽
newRow -= dx;
newRow = Math.max(0, newRow);
}
System.out.println(newRow + " " + newCol);
}
// 기준점을 출발해서 제대로된 쿼리를 다시 실행
int left = newCol;
int right = newCol;
int up = newRow;
int down = newRow;
for (int[] query : queries) { // 쿼리 실행
int dx = query[1]; // 몇 칸
// 이동
if (query[0] == 0) { // 왼쪽
newCol -= dx;
newCol = Math.max(0, newCol);
if (newCol == 0) {
left = 0;
}
} else if (query[0] == 1) { // 오른쪽
newCol += dx;
newCol = Math.min(m - 1, newCol);
if (newCol == m-1) {
right = m - 1;
}
} else if (query[0] == 2) { // 위쪽
newRow -= dx;
newRow = Math.max(0, newRow);
if (newRow == 0) {
up = 0;
}
} else { // 아래쪽
newRow += dx;
newRow = Math.min(n - 1, newRow);
if (newRow == n-1) {
down = n-1;
}
}
}
// 정답 도출
if (newRow == x && newCol == y) {
answer = (long) (right - left + 1) * (down - up + 1);
} else{
answer = 0;
}
return answer;
}
}
주의
- answer를 구할 때 long으로 형변환 하지 않아서 2시간을 허비했다... 꼭 꼼꼼히 확인해서 잔실수를 줄이자..
- 10억 x 10억의 케이스임을 미리 알고 대비하자.