일단 문제를 보고, 테스트케이스를 통과하자는 생각으로 O(nmq) 복잡도를 가지는 알고리즘으로 작성했다.
for-loop 돌면서 직접 query를 다 실행하는 방식이다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
int rowDir[4] = {0, 0, -1, 1};
int colDir[4] = {-1, 1, 0, 0};
bool simulation(int row, int col, const vector<vector<int>> queries, int x, int y, int n, int m)
{
int nrow = row, ncol = col;
for(int i=0;i<queries.size();i++) {
int dir = queries[i][0];
int dist = queries[i][1];
row = nrow + dist * rowDir[dir];
col = ncol + dist * colDir[dir];
if(row < 0)
row = 0;
else if(row >= n)
row = n - 1;
if(col < 0)
col = 0;
else if(col >= m)
col = m - 1;
nrow = row;
ncol = col;
}
if(nrow == x && ncol == y)
return true;
return false;
}
long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
long long answer = 0;
int size = queries.size();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
int startRow = i;
int startCol = j;
if(simulation(startRow, startCol, queries, x, y, n, m))
answer++;
}
}
return answer;
}위 코드로 제출하면 1번 빼고 모두 시간초과가 난다 ㅋㅋ.
그래서 여기서 든 생각이 Queries의 뒷부분부터 체크하면서 역으로 체크하는 것이다.
즉, t 시간에서의 집합을 k라고 가정하면, t - 1시간에서 query[t - 1]를 수행했을 때, k 집합을 나타낼 수 있는 k - 1 조합을 찾는 것이다.
일단 Queue로 도전했는데, 실패했다.
그래서 프로그래머스 10월 코드챌린지 해설 을 좀 참고했다...
n x m 배열에 모두 공이 가득차있고, query를 수행할때마다 dist만큼 기울인다고 생각하는 것이 베이스다.
즉, 공은 항상 사각형의 형태로 유지된다.
그 이후 쿼리의 뒤부터 역으로 가능 후보군을 찾아가는 것을 덧붙이면 된다.
예를 들어 생각해보면,
n = 3, m = 5, x = 0, y = 1, queries = [[3,1],[2,2],[1,1],[2,3],[0,1],[2,1]] 이면,
row_start = 0, row_end = 0 (x 값)
col_start = 1, col_end = 1 (y 값)
부터 시작한다.
1. [2, 1]
기존에는 행의 번호가 감소하는 방향이였기 때문에, row_end 값이 dist만큼 커져야 한다.
이 때, row_start는 0이기 때문에 그대로 0으로 해야한다.
row_start = 0, row_end = 1
col_start = 1, col_end = 1
즉, 0번 row 혹은 1번 row에 있었다면 [2, 1] 연산 뒤에 0번 row가 되는 것이다.
2. [0, 1]
기존에는 열의 번호가 감소하는 방향이였기 때문에, col_end 값이 dist만큼 커져야 한다.
이 때, col_start는 0이 아니기 때문에 dist만큼 커져야 한다.
row_start = 0, row_end = 1
col_start = 2, col_end = 2
3번부턴 1과 2의 연산을 그대로 해주면 된다.
각 단계에서 나오는 결과 값은 다음과 같다.
1 : [row 0~1][col 1~1]
2 : [row 0~1][col 2~2]
3 : [row 0~1][col 2~2]
4 : [row 0~1][col 1~1]
5 : [row 0~1][col 1~1]
6 : [row 0~1][col 1~1]
그 후 row range : 2, col range : 1 이므로, 이 둘을 곱한 2가 정답이 된다.
사실 Edge Case 처리한다고 삽질 엄청했다 ㅠㅠ... #33, #34가 예외 케이스인데, Boundary Check를 불필요하게 많이 해주면 #33, #34를 절대 통과 못한다.
행/열이 증가/감소 하는 것에 따라서 top, bottom, left, right 중 어느 것을 Boundary Check해줘야 하는지 명확히 구분해야 한다.
주어진 쿼리만으로 x, y에 절대 도착하지 못하는 경우는 0으로 결과값을 리턴해줘야 한다. <- 이것을 쿼리 동작 중에 판단해야 한다!
결과 코드는 다음과 같다.
long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
long long answer = 0;
int size = queries.size();
long long row_start = x, row_end = x;
long long col_start = y, col_end = y;
for(int i=size - 1; i >= 0; i--) {
int dir = queries[i][0];
int dist = queries[i][1];
if(dir == 0) { // 열 다시 증가시킴
if(col_start != 0)
col_start = col_start + dist;
col_end = col_end + dist;
if(col_end > m - 1)
col_end = m - 1;
} else if(dir == 1){ // 열 다시 감소시킴
col_start = col_start - dist;
if(col_start < 0)
col_start = 0;
if(col_end != m - 1)
col_end = col_end - dist;
} else if(dir == 2) { // 행 다시 증가시킴
if(row_start != 0)
row_start = row_start + dist;
row_end = row_end + dist;
if(row_end > n - 1)
row_end = n - 1;
} else if(dir == 3) { // 행 다시 감소시킴
row_start = row_start - dist;
if(row_start < 0)
row_start = 0;
if(row_end != n - 1)
row_end = row_end - dist;
}
if(row_start > n - 1 || row_end < 0 || col_start > m - 1 || col_end < 0)
return answer;
}
answer = (row_end - row_start + 1) * (col_end - col_start + 1);
return answer;
}
