👨💻 문제
✍️ 풀이
플레5 문제다.
실제로 배열의 값을 바꾼다면 아마 시간초과가 날 것이다.
요청의 수가 최대 500000회이다.
격자의 크기가 N*N이고 N은 최대 2000이며, 가장 큰 격자의 최외곽 벨트의 길이는 7996이다.
역시 실제로 돌리면 안 될 듯 하다.
실제로 값을 돌리지 않고, 벨트 별로 돌린 수를 기억해두도록 한다.
입력
배열을 2차원 배열이 아닌 벨트 깊이 당 숫자들로 기억을 한다.
다만 단순히 분리만 하는 것이 아니라 회전하는 방향에 맞게 값을 저장해야 한다.
소용돌이 모양으로 바깥부터 값을 저장한다.
private static int[][] listIdx; // 해당 좌표의 values 상의 인덱스
private static List<Integer>[] belts; // 벨트 당 값
private static int[] beltsMove; // 벨트 당 회전 수
...
listIdx = new int[N][N];
belts = new List[N/2 + 1];
beltsMove = new int[N/2 + 1];
// 원본 배열 입력
int[][] originalArr = new int[N][N];
for (int r=0; r<N; r++) {
st = new StringTokenizer(br.readLine());
for (int c=0; c<N; c++) {
originalArr[r][c] = Integer.parseInt(st.nextToken());
}
}
for (int i=1; i<=N/2; i++) {
belts[i] = new ArrayList<>();
}
// 소용돌이 모양으로 바깥부터 리스트를 채움
boolean[][] visited = new boolean[N][N];
int[] dr = new int[] {0, 1, 0, -1};
int[] dc = new int[] {1, 0, -1, 0};
int r = 0;
int c = 0;
int dir = 0;
while (!visited[r][c]) {
// System.out.printf("%d %d\n", r, c);
visited[r][c] = true;
int d = getDepthByPos(r, c);
listIdx[r][c] = belts[d].size();
belts[d].add(originalArr[r][c]);
int nextR = r + dr[dir];
int nextC = c + dc[dir];
if (nextR >= N || nextR < 0 || nextC >= N || nextC < 0 || visited[nextR][nextC]) {
dir++;
dir%=4;
r += dr[dir];
c += dc[dir];
}
else {
r = nextR;
c = nextC;
}
}좌표로부터 벨트의 깊이를 구하는 공식은 아래와 같다.
x, y 중 외곽으로의 거리가 작은 값이 깊이다.
private static int getDepthByPos(int r, int c) {
return Math.min(Math.abs(r >= N/2 ? N - r : r + 1), Math.abs(c >= N/2 ? N - c : c + 1));
}listIdx는 해당 좌표가 벨트 리스트의 어떤 인덱스에 저장되어 있는지를 기억한다.
2번 동작이나 3번 동작에서 바로 바로 값을 추적할 수 있다.
동작
총 3가지 동작이 있다.
1번 동작
해당 벨트에 회전 수를 추가한다.
벨트에 값을 저장한 방향에 따라 더해야 할 수도 빼야 할 수도 있다.
내 경우엔 회전 수만큼 빼야 했다.
회전 수를 추가한 값이 IndexOutOfBound가 발생하지 않도록 추가적으로 연산해준다.
어차피 값을 추적할 때 다시 나눗셈 연산을 하지만, 값이 음수면 제대로 동작하지 않으며, 값이 비정상적으로 커질 수도 있다.
case 1 :
int beltIdx = Integer.parseInt(st.nextToken());
int beltMoveValue = Integer.parseInt(st.nextToken());
beltsMove[beltIdx] -= beltMoveValue;
if (beltsMove[beltIdx] < 0) {
beltsMove[beltIdx] = belts[beltIdx].size() + (beltsMove[beltIdx] % belts[beltIdx].size());
}
break;3번 동작
좌표가 입력되면 해당 좌표의 벨트를 찾는다.
위에 정의해두었던 메서드를 통해 좌표를 통해 깊이를 추적하고,
벨트의 회전 수를 더해준다.
ListIdx 배열을 통해 해당 깊이 리스트의 알맞은 인덱스를 추적하여 값을 찾을 수 있다.
해당 벨트의 회전 수를 고려하여 알맞는 값을 반환한다.
case 3 :
int r0 = Integer.parseInt(st.nextToken()) - 1;
int c0 = Integer.parseInt(st.nextToken()) - 1;
int depth = getDepthByPos(r0, c0);
int idx = (listIdx[r0][c0] + beltsMove[depth]) % belts[depth].size();
int result = belts[depth].get(idx);
sb.append(result);
sb.append('\n');
break;2번 동작
3번 동작을 통해 리스트 및 인덱스를 추적할 수 있다.
해당하는 값 4개를 바꿔준다.
case 2 :
int r1 = Integer.parseInt(st.nextToken()) - 1;
int c1 = Integer.parseInt(st.nextToken()) - 1;
int r2 = r1 + 1;
int c2 = c1 + 1;
int depth1 = getDepthByPos(r1, c1);
int idx1 = (listIdx[r1][c1] + beltsMove[depth1]) % belts[depth1].size();
int value1 = belts[depth1].get(idx1);
int depth2 = getDepthByPos(r1, c2);
int idx2 = (listIdx[r1][c2] + beltsMove[depth2]) % belts[depth2].size();
int value2 = belts[depth2].get(idx2);
int depth3 = getDepthByPos(r2, c1);
int idx3 = (listIdx[r2][c1] + beltsMove[depth3]) % belts[depth3].size();
int value3 = belts[depth3].get(idx3);
int depth4 = getDepthByPos(r2, c2);
int idx4 = (listIdx[r2][c2] + beltsMove[depth4]) % belts[depth4].size();
int value4 = belts[depth4].get(idx4);
belts[depth1].set(idx1, value3);
belts[depth2].set(idx2, value1);
belts[depth3].set(idx3, value4);
belts[depth4].set(idx4, value2);
break;📄 전체 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class _21322 {
private static int N, M;
private static int[][] listIdx; // 해당 좌표의 values 상의 인덱스
private static List<Integer>[] belts; // 벨트 당 값
private static int[] beltsMove; // 벨트 당 회전 수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
listIdx = new int[N][N];
belts = new List[N/2 + 1];
beltsMove = new int[N/2 + 1];
int[][] originalArr = new int[N][N];
for (int r=0; r<N; r++) {
st = new StringTokenizer(br.readLine());
for (int c=0; c<N; c++) {
originalArr[r][c] = Integer.parseInt(st.nextToken());
}
}
for (int i=1; i<=N/2; i++) {
belts[i] = new ArrayList<>();
}
// 소용돌이 모양으로 바깥부터 리스트를 채움
boolean[][] visited = new boolean[N][N];
int[] dr = new int[] {0, 1, 0, -1};
int[] dc = new int[] {1, 0, -1, 0};
int r = 0;
int c = 0;
int dir = 0;
while (!visited[r][c]) {
// System.out.printf("%d %d\n", r, c);
visited[r][c] = true;
int d = getDepthByPos(r, c);
listIdx[r][c] = belts[d].size();
belts[d].add(originalArr[r][c]);
int nextR = r + dr[dir];
int nextC = c + dc[dir];
if (nextR >= N || nextR < 0 || nextC >= N || nextC < 0 || visited[nextR][nextC]) {
dir++;
dir%=4;
r += dr[dir];
c += dc[dir];
}
else {
r = nextR;
c = nextC;
}
}
StringBuilder sb = new StringBuilder();
for (int move=0; move<M; move++) {
st = new StringTokenizer(br.readLine());
switch (Integer.parseInt(st.nextToken())) {
case 1 :
int beltIdx = Integer.parseInt(st.nextToken());
int beltMoveValue = Integer.parseInt(st.nextToken());
beltsMove[beltIdx] -= beltMoveValue;
if (beltsMove[beltIdx] < 0) {
beltsMove[beltIdx] = belts[beltIdx].size() + (beltsMove[beltIdx] % belts[beltIdx].size());
}
break;
case 2 :
int r1 = Integer.parseInt(st.nextToken()) - 1;
int c1 = Integer.parseInt(st.nextToken()) - 1;
int r2 = r1 + 1;
int c2 = c1 + 1;
int depth1 = getDepthByPos(r1, c1);
int idx1 = (listIdx[r1][c1] + beltsMove[depth1]) % belts[depth1].size();
int value1 = belts[depth1].get(idx1);
int depth2 = getDepthByPos(r1, c2);
int idx2 = (listIdx[r1][c2] + beltsMove[depth2]) % belts[depth2].size();
int value2 = belts[depth2].get(idx2);
int depth3 = getDepthByPos(r2, c1);
int idx3 = (listIdx[r2][c1] + beltsMove[depth3]) % belts[depth3].size();
int value3 = belts[depth3].get(idx3);
int depth4 = getDepthByPos(r2, c2);
int idx4 = (listIdx[r2][c2] + beltsMove[depth4]) % belts[depth4].size();
int value4 = belts[depth4].get(idx4);
belts[depth1].set(idx1, value3);
belts[depth2].set(idx2, value1);
belts[depth3].set(idx3, value4);
belts[depth4].set(idx4, value2);
break;
case 3 :
int r0 = Integer.parseInt(st.nextToken()) - 1;
int c0 = Integer.parseInt(st.nextToken()) - 1;
int depth = getDepthByPos(r0, c0);
int idx = (listIdx[r0][c0] + beltsMove[depth]) % belts[depth].size();
int result = belts[depth].get(idx);
sb.append(result);
sb.append('\n');
break;
}
}
System.out.print(sb);
}
private static int getDepthByPos(int r, int c) {
return Math.min(Math.abs(r >= N/2 ? N - r : r + 1), Math.abs(c >= N/2 ? N - c : c + 1));
}
}
입니다.