본문 바로가기
algorithm

[JAVA] 2048(Easy) 삼성 기출 문제 (백준 12100)

by onejunu 2020. 9. 1.
반응형

 

전형적인 구현 문제

 

상하좌우를 그대로 구현했는데 

 

다른 사람들 풀이 보니까 rotate 를 구현하고 방향 하나만 구현한 것이 많이 보였다.. 

 

이렇게하면 확실히 코드 길이는 줄어 들듯 하다.

 

내 코드를 보면서 불필요한 부분들이 몇개 발견되었다.

 

먼저 나의 풀이를 소개한다.

 

 


만약 배열의 한줄만 생각한다고 가정하자.

 

[2,2,0,4,4] 의 배열이 있을 때

 

오른쪽으로 이동하면 [0,0,0,4,8]

 

왼쪽으로 이동하면 [4,8,0,0,0] 

 

이렇게 될 것이다. 왼쪽으로 이동할 때 어떻게 풀었는지 보자.

 

똑같은 크기의 0으로 가득차있는 배열 tmp = [0,0,0,0,0] 를 선언및 초기화한다.

 

그리고 비어있는 Deque 한개를 선언하고 boolean으로 ok =true를 선언하여 이전에 합쳐졌는지 안 합쳐졌는지 체크한다. true일 경우만 합칠 수 있음.

 

[2,2,0,4,4] 를 왼쪽에서 부터 살펴본다. 

 

deque가 비어있으면 무조건 넣는다. 

 

1. Deque = [2]

 

2. ok 가 true 이고 deque의 마지막원소와 같으므로 합칠 수 있다. 그래서 deque 마지막을 꺼낸뒤 합친다. 그리고 ok = false 한다.

Deque = [4]

 

3. 0 이므로 넘어간다.

Deque = [4]

 

4. ok 가 false 이므로 deque에 넣는다. ok = true 한다.

Deque = [4,4]

 

5.  ok가 true이며 deque의 마지막 원소와 같으므로 합칠 수 있다. 그래서 deque 마지막을 꺼낸뒤 합친다. 그리고 ok=false 한다.

Deque = [4,8]

 

deque에 있는 원소를 왼쪽에서 부터 차례로 채워주면 끝이다.

 

 


 

개선해야 할 점이 있는 데

 

사실 deque 는 필요없다. 한번의 루프로 바로바로 채워 줄 수 있다.

 

즉 아까의 예를 들어 설명하면

 

arr = [2,2,0,4,4] 와 result =  [0,0,0,0,0] 이 있다고 한다면

 

왼쪽에서 부터 살펴보고 결과물의 배열이 어떻게 변하는지 관찰해본다.

 

idx 를 새로 선언하는데 이는 결과물의 배열에 값이 변하는 곳을 인덱싱 한다.

 

1. result = [2,0,0,0,0]  arr[0] 는 처음은 그대로 넣는다. idx = 0

2. result = [4,0,0,0,0] arr[1] 은 result[idx] 와 같으므로 result[idx] *=2 를 하고 idx++;

3. result = [4,0,0,0,0] arr[2] 가 0이므로 넘어간다.

4. result = [4,4,0,0,0] arr[3] 은 result[idx]==0 이므로 그대로 넣는다. idx 유지

5. result = [4,8,0,0,0] arr[4] 은 result[idx]와 같으므로 result[idx]*=2 를 하고 idx++;

 

이처럼 풀면 훨씬 빠르게 풀수 있다.

 

 

개선 전의 코드를 첨부하고 마무리한다..

 

import java.util.*;

public class Main{

    static int n;
    static int answer;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[][] board = new int[n][n];
        for(int i=0;i<n;i++) {
            board[i] = new int[n];
            for(int j=0;j<n;j++){
                board[i][j]=sc.nextInt();
            }
        }
        dfs(0,board);
        System.out.println(answer);

    }

    public static void dfs(int idx,int[][] board){
        if(idx == 5){
            answer = Math.max(answer,
                    Arrays
                            .stream(board)
                            .flatMapToInt(Arrays::stream)
                            .max()
                            .getAsInt()
            );

        }
        else{
            dfs(idx+1,up(board));
            dfs(idx+1,down(board));
            dfs(idx+1,right(board));
            dfs(idx+1,left(board));
        }
    }

    public static int[][] up(int[][] board){
        int[][] tmp = new int[n][n];
        for(int i=0;i<n;i++) tmp[i] = new int[n];
        for(int j=0;j<n;j++){
            Deque<Integer> list = new ArrayDeque<>();
            boolean ok = true;
            for(int i=0;i<n;i++){
                if(board[i][j]!=0) {
                    if (list.size() == 0) list.addLast(board[i][j]);
                    else {
                        int last = list.peekLast();
                        if (last == board[i][j] && ok) {
                            list.pollLast();
                            list.addLast(last * 2);
                            ok = false;
                        } else {
                            list.addLast(board[i][j]);
                            ok = true;
                        }
                    }
                }
            }
            int i =0;
            while(!list.isEmpty()){
                tmp[i++][j]=list.poll();
            }
        }
        return tmp;
    }
    public static int[][] down(int[][] board){
        int[][] tmp = new int[n][n];
        for(int i=0;i<n;i++) tmp[i] = new int[n];
        for(int j=0;j<n;j++){
            Deque<Integer> list = new ArrayDeque<>();
            boolean ok = true;
            for(int i=n-1;i>=0;i--){
                if(board[i][j]!=0) {
                    if (list.size() == 0) list.addLast(board[i][j]);
                    else {
                        int last = list.peekLast();
                        if (last == board[i][j] && ok) {
                            list.pollLast();
                            list.addLast(last * 2);
                            ok = false;
                        } else {
                            list.addLast(board[i][j]);
                            ok = true;
                        }
                    }
                }
            }
            int i =n-1;
            while(!list.isEmpty()){
                tmp[i--][j]=list.poll();
            }
        }
        return tmp;
    }

    public static int[][] right(int[][] board){
        int[][] tmp = new int[n][n];
        for(int i=0;i<n;i++) tmp[i] = new int[n];
        for(int i=0;i<n;i++){
            Deque<Integer> list = new ArrayDeque<>();
            boolean ok = true;
            for(int j=n-1;j>=0;j--){
                if(board[i][j]!=0) {
                    if (list.size() == 0) list.addLast(board[i][j]);
                    else {
                        int last = list.peekLast();
                        if (last == board[i][j] && ok) {
                            list.pollLast();
                            list.addLast(last * 2);
                            ok = false;
                        } else {
                            list.addLast(board[i][j]);
                            ok = true;
                        }
                    }
                }
            }
            int j =n-1;
            while(!list.isEmpty()){
                tmp[i][j--]=list.poll();
            }
        }
        return tmp;
    }
    public static int[][] left(int[][] board){
        int[][] tmp = new int[n][n];
        for(int i=0;i<n;i++) tmp[i] = new int[n];
        for(int i=0;i<n;i++){
            Deque<Integer> list = new ArrayDeque<>();
            boolean ok = true;
            for(int j=0;j<n;j++){
                if(board[i][j]!=0) {
                    if (list.size() == 0) list.addLast(board[i][j]);
                    else {
                        int last = list.peekLast();
                        if (last == board[i][j] && ok) {
                            list.pollLast();
                            list.addLast(last * 2);
                            ok = false;
                        } else {
                            list.addLast(board[i][j]);
                            ok = true;
                        }
                    }
                }
            }
            int j =0;
            while(!list.isEmpty()){
                tmp[i][j++]=list.poll();
            }
        }
        return tmp;
    }
}

 

 

 

반응형

태그

, , ,

댓글0