BOJ17140_이차원배열과연산_못푼문제

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

문제요약

1. 1초가 지날때마다 배열에 연산이 적용된다.

2. R연산 : 배열 A의 모든 행에 대해서 정렬을 수행한다 , 행의 개수 >= 열의 개수인 경우에 적용한다.

C연산 : 배열 A의 모든 열에 대해서 정렬을 수행한다 , 행의 개수 < 열의 개수인 경우에 적용한다.

3. 한 행 또는 한 열에 있는 수를 정렬하려면 각각의 수가 몇 번 나왔는지 알아야 한다.

4. 정렬 : 수의 등장 횟수가 커지는 순으로 , 그러한 것이 여러개면 수가 커지는 순으로 정렬한다.

5. 배열 A에 정렬된 결과를 다시 넣는다 , 수와 등장 횟수를 모두 넣는다 , 순서는 수가 먼저이다.

6. 정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 커질 수 있다.

R연산 C연산 각각 가장 큰 행 , 열을 기준으로 모든 행 또는 열의 크기가 커진다.

7. 행 또는 열의 크기가 커진 곳에는 0이 채워진다 , 수를 정렬할 때는 0은 무시해야 한다.

8. 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

- 만약 이번 연산에서 행의 크기가 102가 되면 100개까지만 사용한다는 말인지???

9. 배열 A에 들어있는 수와 r,c,k가 주어졌을 때 , A[r][c] = k가 되기 위한 최소시간을 구하여라

문제issue

1. 연산 수행

(1) 한 행 또는 한 열의 숫자를 count배열에 카운트 해준다.

(2) 정렬규칙에 맞게 temp[][]에 갱신해준다 , temp[][]는 가장 큰 범위로 잡아준다.

(3) 모든 행 또는 모든 열에 대한 정렬이 끝나고 행 또는 열 중에서 가장 큰 size를 구한다 , temp에서 0이 나오기 전까지가 size에 해당한다.

(4) A배열을 size에 맞게 다시 선언해주고 temp를 A배열에 갱신해준다.

2. 정렬

(1) 한 행 또는 한 열의 count배열에 카운트 해준다.

(2) 카운트된 값 중에서 가장 작은 값의 인덱스와 카운트 값을 temp에 갱신 해준다 , 카운트된 값이 같은 경우에는 인덱스를 비교해준다 , temp에 갱신 한 후 해당 count배열은 0으로 만들어준다.

해결흐름

1. A[r][c] = k 인지 확인한다 (A배열의 크기가 계속 변하기 때문에 temp[r][c] = k 인지 확인하도록 하였다.)

2. 배열A의 행 크기와 열크기를 비교해서 R연산 또는 C연산을 수행한다.

3. 배열A를 갱신한다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] a = new int[4][4];
        int[][] temp = new int[101][101];
        for (int i = 1; i < 4; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            for (int j = 1; j < 4; j++) {
                int number = Integer.parseInt(st.nextToken());
                a[i][j] = number;
                temp[i][j] = number;
            }
        }
 
        int cnt = 0;
        while (true) {
//            System.out.println(a.length);
//            System.out.println(a[1].length);
            
            if (temp[r][c] == k)
                break;
            cnt++;
            if(cnt >= 100) {
                System.out.println(-1);
                return;
            }
            // a배열의 행 크기와 열 크기를 비교해서 R연산 또는 C연산을 수행
            int[] count = new int[101]; // a배열에 들어있을 수 있는 수가 100까지
            temp = new int[101][101];
            if (a.length-1 >= a[1].length-1) {
                // R연산
                for (int i = 1; i < a.length; i++) {
                    for (int j = 1; j < a[1].length; j++) {
                        if (a[i][j] != 0) {
                            count[a[i][j]]++;
                        }
                    }
                    int index = 0;
                    int idx = 1;
                    int idx2 = 2;
                    while (true) {
                        int min = Integer.MAX_VALUE;
                        boolean flag = false;
                        for (int k1 = 1; k1 < 101; k1++) {
                            if (count[k1] != 0 && min > count[k1]) {
                                min = count[k1];
                                index = k1;
                                flag = true;
                            }
                        }
                        // count에 0만 남았음
                        if(!flag)
                            break;
                        count[index] = 0;
                        temp[i][idx] = index;
                        temp[i][idx2] = min;
                        idx += 2;
                        idx2 += 2;
                    }
                }
                // temp의 행 중에서 가장 큰 size를 구해서 a배열 재생성 및 갱신
                int max_size = Integer.MIN_VALUE;
                for (int i = 1; i <= a.length; i++) {
                    int temp_size = 0;
                    for (int j = 1; j < 101; j++) {
                        if(temp[i][j] == 0)
                            break;
                        temp_size++;
                    }
                    if(max_size < temp_size)
                        max_size = temp_size;
                }
                if(max_size <= 100) {
                    a = new int[a.length][max_size+1];
                    for (int i = 1; i < a.length; i++) {
                        for (int j = 1; j <= max_size; j++) {
                            a[i][j] = temp[i][j];
                        }
                    }
//                    System.out.println("===============");
//                    for (int i = 1; i < a.length; i++) {
//                        System.out.println(Arrays.toString(a[i]));
//                    }
                }
            } else if (a.length-1 < a[1].length-1) {
                // C연산
                for (int i = 1; i < a[1].length; i++) {
                    for (int j = 1; j < a.length; j++) {
                        if (a[j][i] != 0) {
                            count[a[j][i]]++;
                        }
                    }
                    int index = 0;
                    int idx = 1;
                    int idx2 = 2;
                    while (true) {
                        int min = Integer.MAX_VALUE;
                        boolean flag = false;
                        for (int k1 = 1; k1 < 101; k1++) {
                            if (count[k1] != 0 && min > count[k1]) {
                                min = count[k1];
                                index = k1;
                                flag = true;
                            }
                        }
                        if(!flag)
                            break;
                        count[index] = 0;
                        temp[idx][i] = index;
                        temp[idx2][i] = min;
                        idx += 2;
                        idx2 += 2;
                    }
                }
                int max_size = Integer.MIN_VALUE;
                for (int i = 1; i <= a[1].length; i++) {
                    int temp_size = 0;
                    for (int j = 1; j < 101; j++) {
                        if(temp[j][i] == 0)
                            break;
                        temp_size++;
                    }
                    if(max_size < temp_size)
                        max_size = temp_size;
                }
                if(max_size <= 100) {
                    a = new int[max_size+1][a[1].length];
                    for (int i = 1; i < a[1].length; i++) {
                        for (int j = 1; j <= max_size; j++) {
                            a[j][i] = temp[j][i];
                        }
                    }
//                    System.out.println("===============");
//                    for (int i = 1; i < a.length; i++) {
//                        System.out.println(Arrays.toString(a[i]));
//                    }
                }
            }
//            System.out.println(a.length);
//            System.out.println(a[1].length);
        }
        if(cnt <= 100) {
            System.out.println(cnt);
        }
 
    } // end of main
} // end of class