[프로그래머스][C++] 공 이동 시뮬레이션
공 이동 시뮬레이션
문제 링크
분석
임의의 위치에서 쿼리를 실행하였을 때, 도착 지점에 도착하는 시작 지점의 개수를 구해야합니다.
격자의 크기가 크므로 모든 영역을 탐색할 수 없습니다.
원하는 위치에 도착하는 시작점인지 알기 위해서는 도착지점부터 역으로 계산하면 됩니다.
즉, 쿼리를 역순으로 진행하여 가능한 시작 지점을 좁혀줍니다.
각 쿼리마다 영역을 확장하거나 이동하고, 영역이 벗어나면 가능한 시작점이 없으므로, 탐색 범위를 줄일 수 있습니다.
풀이
#include <vector>
#include <algorithm>
using namespace std;
long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
// 시작 위치에서부터 가능한 위치의 최소/최대 범위를 long long으로 초기화
long long minX = x;
long long minY = y;
long long maxX = x;
long long maxY = y;
// 쿼리를 역순으로 처리한다.
for(int i = queries.size() - 1; i >= 0; --i)
{
// 명령과 이동 거리
int command = queries[i][0];
int dx = queries[i][1];
// ← 방향이며, 역방향(→)으로 이동한다.
if (command == 0)
{
// 왼쪽 벽에 닿지 않았으면 영역을 오른쪽으로 확장
if (minY > 0)
{
minY += dx;
}
// maxY는 오른쪽으로 dx만큼 이동한 결과지만 격자 크기를 넘으면 안된다.
maxY = min(maxY + dx, static_cast<long long>(m - 1));
// 영역이 격자 오른쪽 범위를 벗어난 경우 도달 불가능하다.
if (minY > m - 1)
{
return 0;
}
}
// → 방향이며, 역방향(←)으로 이동한다.
else if (command == 1)
{
// 오른쪽 벽에 닿지 않았으면 영역을 왼쪽으로 확장
if (maxY < m -1)
{
maxY -= dx;
}
// minY는 왼쪽으로 dx만큼 이동한 결과지만 격자 크기를 넘으면 안된다.
minY = max(minY - dx, 0LL);
// 영역이 격자 왼쪽 범위를 벗어난 경우 도달 불가능하다.
if (maxY < 0)
{
return 0;
}
}
// ↑ 방향이며, 역방향(↓)으로 이동한다.
else if (command == 2)
{
// 위쪽 벽에 닿지 않았으면 영역을 아래로 확장
if (minX > 0)
{
minX += dx;
}
// maxX는 아래쪽으로 dx만큼 이동한 결과지만 격자 크기를 넘으면 안된다.
maxX = min(maxX + dx, static_cast<long long>(n - 1));
// 영역이 격자 아래쪽 범위를 벗어난 경우 도달 불가능하다.
if (minX > n - 1)
{
return 0;
}
}
// ↑ 방향이며, 역방향(↓)으로 이동한다.
else
{
// 아래쪽 벽에 닿지 않았으면 영역을 위로 확장
if (maxX < n - 1)
{
maxX -= dx;
}
// minX는 위쪽으로 dx만큼 이동한 결과지만 격자 크기를 넘으면 안된다.
minX = max(minX - dx, 0LL);
// 영역이 격자 위쪽 범위를 벗어난 경우 도달 불가능하다.
if (maxX < 0)
{
return 0;
}
}
}
return (maxX - minX + 1) * (maxY - minY + 1);
}
쿼리를 반대로 적용하면서 범위를 확장하거나 이동합니다.
만약 이때 범위가 격자를 벗어난다면 도달이 불가능한 경우입니다.
가능한 범위의 좌표 수를 곱해서 반환합니다.
성능 요약
시간 복잡도는 $O(q)$입니다.
- 쿼리를 역순으로 처리하는 반복문 $O(q)$
공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.
테스트 성능
테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.08ms, 4.21MB)
테스트 3 〉 통과 (0.08ms, 4.16MB)
테스트 4 〉 통과 (0.08ms, 4.18MB)
테스트 5 〉 통과 (6.53ms, 21.3MB)
테스트 6 〉 통과 (13.71ms, 39.9MB)
테스트 7 〉 통과 (10.52ms, 30.6MB)
테스트 8 〉 통과 (10.42ms, 30.5MB)
테스트 9 〉 통과 (10.76ms, 31.8MB)
테스트 10 〉 통과 (9.13ms, 27.3MB)
테스트 11 〉 통과 (7.69ms, 23.3MB)
테스트 12 〉 통과 (10.26ms, 30.5MB)
테스트 13 〉 통과 (10.52ms, 30.5MB)
테스트 14 〉 통과 (10.70ms, 31.8MB)
테스트 15 〉 통과 (13.87ms, 39.5MB)
테스트 16 〉 통과 (13.76ms, 39.5MB)
테스트 17 〉 통과 (13.80ms, 39.4MB)
테스트 18 〉 통과 (15.93ms, 39.5MB)
테스트 19 〉 통과 (14.80ms, 39.5MB)
테스트 20 〉 통과 (19.23ms, 39.1MB)
테스트 21 〉 통과 (14.04ms, 39.1MB)
테스트 22 〉 통과 (13.92ms, 39.4MB)
테스트 23 〉 통과 (13.97ms, 39.5MB)
테스트 24 〉 통과 (14.04ms, 39.5MB)
테스트 25 〉 통과 (0.07ms, 4.16MB)
테스트 26 〉 통과 (0.28ms, 4.19MB)
테스트 27 〉 통과 (0.13ms, 3.91MB)
테스트 28 〉 통과 (0.02ms, 4.17MB)
테스트 29 〉 통과 (0.06ms, 4.21MB)
테스트 30 〉 통과 (0.04ms, 4.16MB)
테스트 31 〉 통과 (0.04ms, 3.65MB)
테스트 32 〉 통과 (0.36ms, 4.09MB)
테스트 33 〉 통과 (11.43ms, 37.8MB)
테스트 34 〉 통과 (6.00ms, 22MB)
댓글남기기