[백준] 17140 이차원 배열과 연산(Java)

문제링크

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

문제분석

• 배열의 index는 1부터 시작한다.
• 1초마다 연산
• 연산은 R,C 2종류의 연산이 있다.
  -행 크기 >= 열 크기 => R연산
  -행 크기 < 열 크기 => C연산
• 연산
  1. 각 행또는 열에서 각각의 수가 몇번 나왔는지 센다.
  2. 정렬
     • 카운트에 대해 오름차순 정렬
     • 카운트가 같으면, 숫자에 대해 오름차순 정렬
  3. 배열에 넣기
     • [수, 등장 횟수] 순으로 넣는다.
  4. 가장 큰 행, 열 기준으로 크기가 변한다.
  5. 연산에서 숫자 0은 카운트 하지 않는다.
  6. 배열의 크기가 100 넘어가면 버린다.

입력

• r, c, k (1<= r, c, k <=100)
• 3개의 줄에 배열 A에 들어있는 수(<=100)

출력

• A[r][c]에 들어있는 값이 k가 되기 위한 연상의 최소 시간을 출력한다.
• 100초가 지나도 A[r][c]=k가 되지 않으면 -1을 출력한다.

풀이

조건에 맞게 R, C 연산을 작성하면 된다.

• HashMap으로 행 or 열에 있는 각 숫자의 개수를 Counting 한다.
• 정렬을 위해 ArrayList에 담은 후, 정렬을 수행
• 현재 행, 열 크기보다 연산 결과가 크다면 배열의 크기 업데이트(크기는 100을 넘지 않는다)
• 정렬된 결과를 배열에 옮겨 담는다([숫자, 개수] 순서로 담는다)
  • 최대 100개까지만 담고 나머지는 버린다.
  • 주의!! 연산 후 크기가 감소할 수도 있다. (3, 3, 3)->(3, 3)
  • 따라서 감소한 경우에 빈 자리를 '0'으로 채워 넣어야 한다.

코드

import java.util.*;

//정렬을 위한 클래스 선언
class Operation implements Comparable<Operation>{
    int num;
    int count;

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

    //정렬 기준에 따라 정렬
    //개수가 같은 경우 -> 숫자로 오름차순
    //개수가 다른 경우 -> 개수로 오름차순
    public int compareTo(Operation b){
        if(this.count==b.count) return this.num-b.num;
        else return this.count-b.count;
    }
}

class Arr{
    //배열의 크기를 저장할 변수
    int r, c;
    int[][] arr = new int[101][101];

    //초기에 배열의 크기는 3x3이다.
    public Arr() {
        this.r = 3;
        this.c = 3;
    }

    void R(){
        for(int i=1; i<=r; i++){
            //HashMap을 이용해 각 숫자의 개수를 counting한다.
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int j=1; j<=c; j++){
                if(arr[i][j]!=0)
                    map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
            }
            //정렬을 위해 list에 옮겨 담는다.
            ArrayList<Operation> list = new ArrayList<>();
            Iterator<Integer> it = map.keySet().iterator();
            while (it.hasNext()){
                Integer key = it.next();
                list.add(new Operation(key, map.get(key)));
            }
            //배열의 크기 업데이트
            //크기가 100을 초과하지는 못한다.
            c = Math.max(c, list.size()*2);
            c = Math.min(c, 100);

            Collections.sort(list);//정렬

            //배열에 연산 결과를 옮겨 담는다.
            int currentC = 1;
            for (Operation operation : list) {
                arr[i][currentC] = operation.num;
                arr[i][currentC+1] = operation.count;
                currentC+=2;
                //처음 100개를 제외한 나머지는 버린다.
                if(currentC>99) break;
            }
            //주의 - 연산 후 크기가 감소할 수 있다.
            for(int j=currentC; j<=c; j++){
                arr[i][j] = 0;
            }
        }
    }

    //R 연산과 동일한 방법으로 진행
    void C(){
        for(int j=1; j<=c; j++){
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i=1; i<=r; i++){
                if(arr[i][j]!=0)
                    map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
            }
            ArrayList<Operation> list = new ArrayList<>();
            Iterator<Integer> it = map.keySet().iterator();
            while (it.hasNext()){
                Integer key = it.next();
                list.add(new Operation(key, map.get(key)));
            }
            r = Math.max(r, list.size()*2);
            r = Math.min(r, 100);
            Collections.sort(list);

            int currentR = 1;
            for (Operation operation : list) {
                arr[currentR][j] = operation.num;
                arr[currentR+1][j] = operation.count;
                currentR+=2;
                if(currentR>99) break;
            }

            for(int i=currentR; i<=r; i++){
                arr[i][j] = 0;
            }
        }
    }
}

public class Main {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int answer = 0;
        int r, c, k;
        r = scanner.nextInt();
        c = scanner.nextInt();
        k = scanner.nextInt();

        Arr arr = new Arr();
        for(int i=1; i<=3; i++){
            for(int j=1; j<=3; j++){
                arr.arr[i][j] = scanner.nextInt();
            }
        }

        //A[r][c]가 k가 될때까지 반복
        while(arr.arr[r][c]!=k){
            //조건에 맞게 R또는 C연산을 수행한다.
            if(arr.r>=arr.c) arr.R();
            else arr.C();
            answer++;
            //답이 100을 넘어가면 -1을 출력
            if(answer>100){
                answer=-1;
                break;
            }
        }
        System.out.println(answer);
    }
}