이차원 배열과 연산

📍 문제 설명

 

 

💡 접근

생각보다 복잡해서 꽤나 시간을 많이 썼다.

1.계수 정렬로 값, 등장 횟수를 구하고 해당 필드를 갖는 클래스를 만들어서 정렬기준에 따라 정렬한다.

2.새로운 배열에 list 사이즈의 2배(값, 등장 횟수를 배열에 넣어야하므로)로 초기화한다.

3.해당 배열을 int[] 형 리스트에 담아놓고 새로운 배열을 만든다.

 

추가 조건을 잘못넣었었는데, 배열의 길이가 3x3보다 작을 때 0을 3x3만큼 채워줘야 하는가이다.

해당 조건은 값이 맞는지 찾는 지점보다 크기가 작은 배열이 들어올 때 ArrayIndex~ 에러가 나서 넣어줬었는데,

그냥 값이 맞는지 찾는 지점에 해당 지점보다 크기가 작으면 안된다는 조건을 넣어줌으로써 해결했다.

 

 

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k, answer, cnt, max, min, second;
    static int[][] board, clone, dis;
    static boolean[][] visited;
    static int[] ch, pm, combi, graph, temp;
    static boolean flag = false;
    static int[] dx = {-1,0,1,0,}; //북동남서
    static int[] dy = {0,1,0,-1};
    static int[] count = new int[101];
    static ArrayList<Point> list;
    static ArrayList<int[]> tempList;
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        k = kb.nextInt(); //찾아야하는 수
        board = new int[3][3];
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        T.solution();
    }

    private void solution() {
        if(second > 100) {
            System.out.println(-1);
            return;
        }
        //해당 위치에서 값을 찾으면 리턴
        if(n-1 < board.length && m-1 < board[0].length && board[n-1][m-1] == k) {
            System.out.println(second);
            System.exit(0);
        }
        //행의 크기는 100을 넘을 수 없다.
        if(board.length >= 100) {
            int[][] newBoard = new int[100][board[0].length];
            for(int i = 0; i < 100; i++) {
                for(int j = 0; j < board[0].length; j++) {
                    newBoard[i][j] = board[i][j];
                }
            }
            board = newBoard;
        }
        //열의 크기는 100을 넘을 수 없다.
        if(board[0].length >= 100) {
            int[][] newBoard = new int[board.length][100];
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < board[0].length; j++) {
                    newBoard[i][j] = board[i][j];
                }
            }
            board = newBoard;
        }

        //계수정렬로 값, 등장 횟수를 구하고 값, 등장횟수를 갖는 클래스를 만들어서 정렬 시킨다음 정렬된 결과를 리스트에 담는다.
        tempList = new ArrayList<>();

        //r연산 - 모든 행 정렬
        if(board.length >= board[0].length) {
            max = 0;
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < board[0].length; j++) {
                    if(board[i][j] != 0) count[board[i][j]]++;
                }
                list = new ArrayList<>();
                for(int j = 0; j < 101; j++) {
                    if(count[j] != 0) list.add(new Point(j, count[j]));
                }
                Collections.sort(list);
                //list의 2배 만큼 배열을 만들기(숫자, 등장횟수를 넣어야함)
                temp = new int[list.size() * 2];
                //0일 때 0,1 1일 때 2,3이 들어가야한다!
                int j = 0;
                int k = 0;
                for(; j < temp.length; j++) {
                    temp[j++] = list.get(k).number;
                    temp[j] = list.get(k).cnt;
                    k++;
                }
                max = Math.max(max, temp.length);
                tempList.add(temp);
                count = new int[101];
            }

            //해당 max값 기준으로 배열을 새로 생성 - 열이 추가가 됨
            board = new int[board.length][max];
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < tempList.get(i).length; j++) {
                    board[i][j] = tempList.get(i)[j];
                }
            }
            tempList = null;
        }

        //c 연산 - 모든 열 정렬
        else {
            max = 0;
            for(int i = 0; i < board[0].length; i++) {
                for(int j = 0; j < board.length; j++) {
                    if(board[j][i] != 0) count[board[j][i]]++;
                }
                list = new ArrayList<>();
                for(int j = 0; j < 101; j++) {
                    if(count[j] != 0) list.add(new Point(j, count[j]));
                }
                Collections.sort(list);
                temp = new int[list.size() * 2];

                int j = 0;
                int k = 0;
                for(; j < temp.length; j++) {
                    temp[j++] = list.get(k).number;
                    temp[j] = list.get(k).cnt;
                    k++;
                }
                max = Math.max(max, temp.length);
                tempList.add(temp);
                count = new int[101];
            }

            //해당 max값 기준으로 배열을 새로 생성 - 행이 추가가 됨
            board = new int[max][board[0].length];
            for(int i = 0; i < board[0].length; i++) {
                for(int j = 0; j < tempList.get(i).length; j++) {
                    board[j][i] = tempList.get(i)[j];
                }
            }
            tempList = null;
        }
        second++;
        solution();
    }


    private static class Point implements Comparable<Point> {
        private int number;
        private int cnt;

        public Point(int number, int cnt) {
            this.number = number;
            this.cnt = cnt;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "number=" + number +
                    ", cnt=" + cnt +
                    '}';
        }

        @Override
        public int compareTo(Point o) {
            if(this.cnt == o.cnt) return this.number - o.number;
            else return this.cnt - o.cnt;
        }
    }
}