[SWEA] 6109번 자바(Java) 추억의 2048게임
풀이
백준의 2048문제와 다르게 상하좌우중에 한 방향으로 한번만 이동하면 되는 문제이다. 따라서 100개 케이스 2초 즉 1케이스당 200만 복잡도까지 사용가능하다.
방향을 입력받고 각 방향에 맞게 블럭을 이동시켜주면 된다. 이 과정을 투포인터로 할수도 있고 Queue를 사용할 수도 있다. 본인은 Deque을 사용해서 해당블록들이 합해지는 기록을 했다. 아래 이미지는 첫번째 케이스의 첫 열이 Queue에 들어오는과정을 설명한다. 중요한점은 3가지 조건을 생각해야한다.
- Queue가 비어있는가? -> 비어있다면 해당 칸값 바로 추가
- 칸의 값이 0인가? -> 추가X
- 바로 이전에 값이 합쳐졌는가?(이 조건을 안넣으면 계속해서 칸의 합이 합쳐진다.) -> 다음칸은 그냥 Queue에 추가
이후에는 Queue에서 순차적으로 값을 뽑아서 map해당열의 0 ~ N-1까지 칸을 다시 채워준다
이제 각 방향에 맞게 파라미터만 변경해서 진행하면 된다.
공통된 코드가 많아서 이걸 하나의 메서드로 줄일 수 있다. 이를 위해 고려할점은 2가지이다.
- 이동방향: 상하, 좌우
- 이동크기: 1, -1
이를 고려해서 코드를 짜게될때 파라미터로 (방향, 시작 index, 끝 index, 이동크기)를 줘야한다.
이렇게 코드를 짜면 4개 방향을 한 메서드로 구현할 수 있다.
예제 입력 예시
2
5 up //테스트케이스 개수
4 8 2 4 0 //첫 번째 테스트 케이스, N = 5
4 4 2 0 8
8 0 2 4 4
2 2 2 2 8
0 2 2 0 0
2 down //두 번째 테스트 케이스, N = 2
16 2
0 2
예제 출력 예시
#1 //첫번째 테스트 케이스
8 8 4 8 8
8 4 4 2 4
2 4 2 0 8
0 0 0 0 0
0 0 0 0 0
#2 //두번째 테스트 케이스
0 0
16 4
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Solution {
private static int N;
private static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st;
for (int t = 0; t < T; t++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
String di = st.nextToken();
// map입력받기
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
sb.append("#").append(t + 1).append("\n");
if (di.equals("up")) play2048(false, 0, N, 1);
else if(di.equals("down")) play2048(false, N-1, -1, -1);
else if(di.equals("right")) play2048(true, N-1, -1, -1);
else play2048(true, 0, N, 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(map[i][j]).append(" ");
}
sb.append("\n");
}
}
System.out.println(sb);
}
private static void play2048(boolean goX, int s, int e, int m) {
int ys = 0;
int xs = 0;
if(goX)xs = s;
else ys = s;
while(!((goX)? ys == N: xs == N)) {
Deque<Integer> d = new LinkedList<>();
boolean flag = false; //true면 이전에서 합쳐진경우
if(goX) xs = s;
else ys = s;
while(!((goX)? xs == e: ys == e)) {
if(map[ys][xs] == 0) {}
else if(d.isEmpty()) d.add(map[ys][xs]); // 비어있는 경우
else if(flag||d.peekLast() != map[ys][xs]) { // 이전에서 합쳐진 경우 또는 현개값과 스택의 peek이 다른경우
d.add(map[ys][xs]);
flag = false;
}
else if(map[ys][xs] != 0){ //flag가 false이고 같은 경우
d.add(d.pollLast()*2);
flag = true;
}
map[ys][xs] = 0;
if(goX) xs+=m;
else ys+=m;
}
//빈칸 채워주기
if(goX) {
int xIdx = s;
while(!d.isEmpty()){
map[ys][xIdx] = d.poll();
xIdx+=m;
}
ys++;
}
else{
int yIdx = s;
while(!d.isEmpty()){
map[yIdx][xs] = d.poll();
yIdx+=m;
}
xs++;
}
}
}
}