2 D配列と演算(17140)

1.質問

質問リンク
説明:
サイズ3×3人の列Aがある.配列のインデックスは1から始まります.1秒ごとに演算が配列に適用されます.

R演算:アレイAのすべての行をソートします.行数≧列数の場合に適用されます.

C演算:アレイA内のすべての列をソートします.行数<列数の場合に適用されます.

1行または列の数値をソートするには、各数値が何回発生したかを知る必要があります.次に,数の登場回数が増える順であるが,この場合は多くの点で数の増加順に並べられる.そして、配列Aに並べ替え結果を再配置する必要がある.並べ替えた結果を並べ替えに入れると、数字も出場回数も入れて、順番は数字が優先されます.
例えば,[3,1,1]では3が1回,1が2回出現する.したがって,並べ替えの結果は[3,1,2]であった.この配列では、3が1番、1が2番、2が1番で登場します.再ソートは[2,1,3,1,2]になります.
ソート結果を配列に戻すと、行または列のサイズが異なる場合があります.R演算では、最大行に応じてすべての行のサイズが変更されます.C演算では、最大列に基づいてすべての列のサイズが変更されます.行または列のサイズが大きくなる場合は、0を入力します.数値をソートする場合は、0を無視します.例えば、[3,2,0,0]を並べ替えた結果は、[3,2]を並べ替えた結果と同じである.
行または列のサイズが100を超える場合、最初の100以外の行または列は破棄されます.
配列Aの数字とr,c,kが与えられたとき,A[r][C]の値がkとなる最小時間を求める.
入力
第1行はr,c,kを与える.(1 ≤ r, c, k ≤ 100)
2行目から3行目にAで与えられた数字を並べます.配列Aの数字は100以下の自然数である.
しゅつりょく
演算の最小時間を出力し、A[r][C]の値をkとする.100秒経過してもA[r][c]=kでない場合、−1が出力される.

2.解答

2-1. 条件

個の登場回数が増えた順で、この順は多くの点で数が増えた順に並べられている.

行または列のサイズが100を超えると、最初の100を除いて残りの部分は破棄されます.

2-2. に答える

一見、この問題は難しそうに見えるが、ちょっとした工夫さえすれば、簡単に解決できる.
計画1-必要な変数を宣言します.

// 계획1 - 필요한 변수 선언합니다.
int curR = 3; // 현재 행의 개수
int curC = 3; // 현재 열의 개수
int ans = -1;
		
int[][] A = new int[100][100]; // 100을 넘어가면 버리기 때문에 100 x 100의 배열을 선언했습니다.
int[] cnt = new int[101]; // 수의 등장 횟수를 세는 배열

最初に必要な変数を宣言するプロセスは非常に重要です.
「どうやって問題に近づくの?」で行ないます.
実施の難しさは千差万別で、これは方法にかかっている.
私は2-1で指定した条件のうち、100を超える条件で残りの条件を放棄しました.100 x 100の2 Dアレイのみを宣言し、問題の複雑さを低減しました.
この条件がない場合は、メモリを動的に割り当て、実装するためにListが宣言されている可能性があります.
では、実現の難しさはかなり向上したのではないでしょうか.
そのため、問題をよりよく読み、それに応じて問題に簡単にアクセスする方法を常に見つけなければなりません.
計画2-カウントソート演算を実行します.

// 개수가 커지는 순에서 수가 커지는 순으로 정렬
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

実はこれがコア[수, 수의 등장 횟수]を優先順位キューに入れ、問題の要件に従ってソートします.
計画3—最大100回のR、C演算を行う.
この部分を完全なコードでチェックしましょう.

3.完全なコード

import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws Exception {
		// 계획1 - 필요한 변수들을 선언합니다.
		int curR = 3; // 현재 행의 개수
		int curC = 3; // 현재 열의 개수
		int ans = -1;
		
		int[][] A = new int[100][100]; // 100을 넘어가면 버리기 때문에 100 x 100의 배열을 선언했습니다.
		int[] cnt = new int[101]; // 수의 등장 횟수를 세는 배열
		
		// 계획2 - 수의 정렬 연산을 구현합니다.
		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
		
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		int R = Integer.parseInt(stk.nextToken()) - 1;
		int C = Integer.parseInt(stk.nextToken()) - 1;
		int K = Integer.parseInt(stk.nextToken());
		
		for (int i = 0; i < 3; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				A[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		
		// 계획3 - 최대 100번의 R, C연산을 진행합니다.
		for (int i = 0; i <= 100; i++) {
			// 답을 찾았을 때
			if (A[R][C] == K) {
				ans = i;
				break;
			}
			
			// R연산
			if (curR >= curC) {
				int nextC = -1; // R연산으로 인해 바뀔 열의 길이
				
				for (int j = 0; j < curR; j++) {
					// 한 행에 대하여 수의 등장 횟수를 셉니다.
					for (int k = 0; k < curC; k++) {
						if (A[j][k] != 0) {
							cnt[A[j][k]]++;
						}
					}
					
					// 등장한 수들을 우선순위큐에 넣습니다.
					for (int k = 1; k <= 100; k++) {
						if (cnt[k] != 0) {
							pq.add(new int[] {k, cnt[k]});
							cnt[k] = 0; // 다시 0으로 초기화
						}
					}
					
					// 다음 열의 길이는 [수, 수의 등장 횟수], [수, 수의 등장 횟수]를
					// [수, 수의 등장 횟수, 수, 수의 등장 횟수]로 평탄화 시켜야 하니까 pq.size() * 2가 됩니다.
					nextC = Math.max(nextC, pq.size() * 2);
					
					int idx = 0;
					
					// 정렬한 결과를 현재 행에 덮어씌웁니다.
					while (!pq.isEmpty()) {
						int[] n = pq.poll();
						A[j][idx++] = n[0];
						A[j][idx++] = n[1];
					}
					
					// 남은 부분은 0으로 초기화 합니다.
					for (int k = idx; k <= curC; k++) {
						A[j][k] = 0;
					}
				}
				
				// 100 이후는 버립니다.
				curC = Math.min(nextC, 100);
			}
			// C연산
			else {
				int nextR = -1;
				
				for (int j = 0; j < curC; j++) {
					for (int k = 0; k < curR; k++) {
						if (A[k][j] != 0) {
							cnt[A[k][j]]++;
						}
					}
					
					for (int k = 1; k <= 100; k++) {
						if (cnt[k] != 0) {
							pq.add(new int[] {k, cnt[k]});
							cnt[k] = 0;
						}
					}
					
					nextR = Math.max(nextR, pq.size() * 2);
					
					int idx = 0;
					
					while (!pq.isEmpty()) {
						int[] n = pq.poll();
						A[idx++][j] = n[0];
						A[idx++][j] = n[1];
					}
					
					for (int k = idx; k <= curR; k++) {
						A[k][j] = 0;
					}
				}
				
				curR = Math.min(nextR, 100);
			}
		}
		
		bw.write(ans + "");
		bw.close();
	}
}