백준, 이차원 배열과 연산(17140, java), 75%에서 틀리는 이유

문제 설명

크기가 3x3인 배열이 있다. 이때 행의 개수가 열의 개수보다 크거나 같으면 행을 기준으로 정렬하고 반대이면 열을 기준으로 정렬을 한다.

이때 정렬의 기준은 각 수가 얼마나 많이 등장하는지, 만일 같다면 각 수의 크기이다. 예를 들어서 [3, 1, 1]이 있다면 1은 총 2번 나왔고 3은 총 1번 나왔으니 (1, 2), (3, 1) 이렇게 정렬이 되는 것이다. 이때 정렬은 수를 먼저 넣어준다.

 

100초 안쪽으로 위의 정렬을 해줄 건데 arr[r][c]에서 k가 나올 때 얼마나 많은 시간이 걸리는지 구하는 문제이다. 만일 100초를 넘어갔는데 결과를 내지 못한다면 -1을 출력한다.

단, 배열의 수가 0이라면 정렬 대상이 아니다.

 

사실 이 문제는 힌트를 보면 빠르게 이해할 수 있다.

힌트에서 나왔던 대로 아래와 같은 행렬이 존재한다고 생각해보자.

 

1 2 1

2 1 3

3 3 3

 

일단 행의 수가 열의 수와 같으니 R 연산을 해줄 것이다.

각 수와 빈도수를 묶어서 표현하면 아래와 같이 된다.

(1, 2) (2, 1)

(2, 1) (1, 1) (3, 3)

(3, 3)

 

이것을 빈도수와 각 수의 크기로 오름차순 정렬하면 아래와 같이 된다.

(2, 1) (1, 2)

(1, 1) (2, 1) (3, 1)

(3, 3)

 

그래서 이를 행렬로 만들면 아래와 같은 2차원 배열이 나온다.

2 1 1 2 0 0

1 1 2 1 3 1

3 3 0 0 0 0

 

C연산은 R연산을 해준 것에서 기준을 열로 잡으면 된다.

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

문제 풀이

배열의 인덱스 고려가 굉장히 중요한 문제다. 

pair 객체

숫자와 해당 숫자의 빈도수를 저장하는 객체를 만들어 준다.

class pair{
    int count;
    int num;

    pair(int count, int num){
        this.count = count;
        this.num = num;
    }
}

R 정렬 함수

배열을 행을 기준으로 정렬해 줄 건데, 이때 배열의 정확한 크기를 계산해 넣어주기 보다는 일단 2차원 리스트에 넣어주기를 택했다.

 

먼저 Map을 이용해서 각 행마다 숫자와 빈도수를 구해준다. 이때 값이 0이면 continue를 해준다.

그리고 1차원 리스트를 하나 만들어서 map에 key로 있는 숫자와 value로 있는 빈도수를 pair로 넣어준다. 그리고 빈도수와 숫자의 크기를 오름차순으로 정렬한다. 마지막으로 정렬이 된 1차원 리스트르 2차원 리스트에 넣어준다.

 

위의 2차원 반복문이 끝나면 makeArrR()로 가서 만들어 놓은 2차원 리스트를 배열로 바꾸는 연산을 한다.

    public static void R(int[][] arr){
        ArrayList<ArrayList<pair>> tmpList = new ArrayList<>();

        for(int i=0; i<arr.length; i++) {
            Map<Integer, Integer> map = new HashMap<>();

            for(int j=0; j<arr[0].length; j++){
                if(arr[i][j] == 0){
                    continue;
                }

                map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
            }

            ArrayList<pair> list = new ArrayList<>();
            for(int key : map.keySet()){
                list.add(new pair(map.get(key), key));
            }

            Collections.sort(list, (o1, o2) -> {
                if(o1.count == o2.count){
                    return o1.num - o2.num;
                }
                return o1.count - o2.count;
            });
            tmpList.add(list);
        }

        makeArrR(tmpList);

    }

2차원 리스트를 배열로 만들기

일단 배열은 크기를 미리 정해줘야 한다. 그렇기에 행 부분의 최대 크기를 구한 다음 *2를 해서 크기를 정한다. *2를 해주는 이유는 수와 수의 빈도수가 배열에 들어갈 것이기 때문에 2배를 해서 크기를 늘려줘야 한다.

 

그리고 2차원 반복문을 돌리면서 2차원 배열에 넣어주는데, 이때 행 부분의 인덱스는 따로 index 변수를 만들어서 관리한다. 왜냐하면 반복문에 사용되는 변수는 리스트를 기준으로 하기 때문에 해당 변수를 배열에도 사용한다면 정확한 값이 나오지 않기 때문이다. 

 

그리고 deepCopy() 함수를 이용해서 전역 변수인 arr에 새로 만든 값을 넣어준다.

    public static void makeArrR(ArrayList<ArrayList<pair>> tmpList){
        int maxSize = 0;
        for(int i=0; i<tmpList.size(); i++){
            if(maxSize < tmpList.get(i).size()){
                maxSize = tmpList.get(i).size();
            }
        }


        int[][] newArr = new int[tmpList.size()][maxSize*2];

        for(int i=0; i<tmpList.size(); i++){
            int index = 0;
            for(int j=0; j < tmpList.get(i).size(); j++){
                newArr[i][index] = tmpList.get(i).get(j).num;
                newArr[i][index+1] = tmpList.get(i).get(j).count;
                index += 2;
            }
        }

        deepCopy(newArr);
        //display(newArr);
    }

deepCopy 하기

새로운 배열을 만들어줬으면 기존 배열을 새로운 배열로 만들어서 새로운 배열을 이용하게 해야 한다. 이때 여기서 단순히 '='과 같은 대입 연산자를 사용한다면, 주소가 복사되는 것이지 값이 정확하게 전달되지 않기 때문에 나는 deepCopy라는 함수를 따로 만들어줬다.

 

이 부분은 그냥 전역 변수로 지정되어 있는 arr의 크기를 새로 할당해주고 새 배열의 값을 그대로 넣어주면 된다.

    public static void deepCopy(int[][] copyArr){

        arr = new int[copyArr.length][copyArr[0].length];
        for(int i=0; i<copyArr.length; i++){
            for(int j=0; j<copyArr[0].length; j++){
                arr[i][j] = copyArr[i][j];
            }
        }

        //display();
    }

 

while 문

시간이 100보다 크면 탈출한다. 그리고 arr[r][c] = k이면 time을 출력하고 탈출한다. 이 조건문을 검사할 때 r, c가 현재 arr의 크기를 벗어날 수 있으므로 꼭 r, c가 2차원 배열 안에 들어가 있는지 확인한다.

 

그리고 행의 크기가 더 크거나 같으면 R 정을 열의 크기가 더 크면 C 정렬을 한다. 

        while(true){

            if(time > 100){
                System.out.println("-1");
                break;
            }

            if(r < arr.length && c < arr[0].length){
                if(arr[r][c] == k){
                    System.out.println(time);
                    break;
                }
            }


            if(arr.length >= arr[0].length){
                R(arr);
            }else{
                C(arr);
            }

            time++;
        }

75%에서 틀리는 이유

만일 time이 100보다 크면 -1을 출력하고 탈출한다. 100 이상으로 둔다면 75%에서 막힐 수 있으므로 무조건 100보다 크게 한다.

코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class pair{
    int count;
    int num;

    pair(int count, int num){
        this.count = count;
        this.num = num;
    }
}

public class Main {

    public static int r, c, k;
    public static int[][] arr;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken())-1;
        c = Integer.parseInt(st.nextToken())-1;
        k = Integer.parseInt(st.nextToken());
        int time = 0;

        arr = new int[3][3];

        for(int i=0; i<3; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<3; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
         }

        while(true){

            if(time > 100){
                System.out.println("-1");
                break;
            }

            if(r < arr.length && c < arr[0].length){
                if(arr[r][c] == k){
                    System.out.println(time);
                    break;
                }
            }


            if(arr.length >= arr[0].length){
                R(arr);
            }else{
                C(arr);
            }

            time++;
        }
        

    }

    public static void deepCopy(int[][] copyArr){

        arr = new int[copyArr.length][copyArr[0].length];
        for(int i=0; i<copyArr.length; i++){
            for(int j=0; j<copyArr[0].length; j++){
                arr[i][j] = copyArr[i][j];
            }
        }
        
    }


    public static void makeArrR(ArrayList<ArrayList<pair>> tmpList){
        int maxSize = 0;
        for(int i=0; i<tmpList.size(); i++){
            if(maxSize < tmpList.get(i).size()){
                maxSize = tmpList.get(i).size();
            }
        }


        int[][] newArr = new int[tmpList.size()][maxSize*2];

        for(int i=0; i<tmpList.size(); i++){
            int index = 0;
            for(int j=0; j < tmpList.get(i).size(); j++){
                newArr[i][index] = tmpList.get(i).get(j).num;
                newArr[i][index+1] = tmpList.get(i).get(j).count;
                index += 2;
            }
        }

        deepCopy(newArr);
    }

    public static void makeArrC(ArrayList<ArrayList<pair>> tmpList){
        int maxSize = 0;
        for(int i=0; i<tmpList.size(); i++){
            if(maxSize < tmpList.get(i).size()){
                maxSize = tmpList.get(i).size();
            }
        }


        int[][] newArr = new int[maxSize*2][tmpList.size()];

        for(int i=0; i<tmpList.size(); i++){
            int index = 0;
            for(int j=0; j < tmpList.get(i).size(); j++){
                newArr[index][i] = tmpList.get(i).get(j).num;
                newArr[index+1][i] = tmpList.get(i).get(j).count;
                index += 2;
            }
        }
        deepCopy(newArr);
    }

    //행을 기준으로 정렬
    public static void R(int[][] arr){
        ArrayList<ArrayList<pair>> tmpList = new ArrayList<>();

        for(int i=0; i<arr.length; i++) {
            Map<Integer, Integer> map = new HashMap<>();

            for(int j=0; j<arr[0].length; j++){
                if(arr[i][j] == 0){
                    continue;
                }

                map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
            }

            ArrayList<pair> list = new ArrayList<>();
            for(int key : map.keySet()){
                list.add(new pair(map.get(key), key));
            }

            Collections.sort(list, (o1, o2) -> {
                if(o1.count == o2.count){
                    return o1.num - o2.num;
                }
                return o1.count - o2.count;
            });
            tmpList.add(list);
        }

        makeArrR(tmpList);

    }

    public static void C(int[][] arr){
        ArrayList<ArrayList<pair>> tmpList = new ArrayList<>();

        for(int i=0; i<arr[0].length; i++) {
            Map<Integer, Integer> map = new HashMap<>();

            for(int j=0; j<arr.length; j++){
                if(arr[j][i] == 0){
                    continue;
                }

                map.put(arr[j][i], map.getOrDefault(arr[j][i], 0)+1);
            }

            ArrayList<pair> list = new ArrayList<>();
            for(int key : map.keySet()){
                list.add(new pair(map.get(key), key));
            }
            

            Collections.sort(list, (o1, o2) -> {
                if(o1.count == o2.count){
                    return o1.num - o2.num;
                }
                return o1.count - o2.count;
            });

            tmpList.add(list);
        }

        makeArrC(tmpList);

    }

}