문제
크기가 3×3인 배열 A로 시작하여 매 초마다 다음 연산을 수행한다.
- 행의 수
R≥ 열의 수C이면 R 연산: 각 행에서 등장 횟수를 세어 (수, 등장 횟수) 쌍을 등장 횟수 오름차순, 같으면 수 오름차순으로 정렬 후 배열을 이어 붙인다. R < C이면 C 연산: 각 열에 동일 방식을 적용한다.
각 연산 후 배열의 크기는 최대 100×100을 초과하지 않는다. t초 후 A[r][c] = k가 되는 최소 시간을 구한다. 100초 안에 불가능하면 -1을 출력한다.
입력
첫째 줄에 r, c, k가 주어진다. 이후 3줄에 걸쳐 3×3 배열 값이 주어진다.
출력
최소 시간을 출력한다. 100초 이내에 불가능하면 -1을 출력한다.
예제
입력
1 2 2
1 2 1
2 1 3
3 3 3출력
2풀이
핵심 아이디어: R, C 중 크거나 같은 쪽을 기준으로 각 행/열을 처리하는 시뮬레이션 문제이다. 각 행(또는 열)의 원소별 등장 횟수를 카운팅 배열로 집계한 뒤, 등장 횟수 오름차순 → 원소 오름차순으로 정렬하여 새 배열을 만든다.
- 조건 확인: 매 반복 시작 시
A[r][c] == k이면 현재 시간 반환. - R 연산 (
R >= C): 각 행i에 대해count[v]로 빈도를 센다. 빈도 오름차순 → 수 오름차순으로 (수, 빈도) 쌍을 나열해 해당 행에 덮어쓴다. 새 길이의 최대값이 새C가 된다. - C 연산 (
R < C): 각 열j에 대해 동일하게 처리. 새 길이의 최대값이 새R이 된다. - 크기 제한: 100 초과 시 100으로 클리핑한다.
- 종료: 100번 반복 후에도 조건 미충족 시 -1을 출력한다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day346BOJ17140이차원배열과연산 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken()) - 1;
int k = Integer.parseInt(st.nextToken());
int[][] A = new int[100][100];
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
int time = 0;
int R = 3, C = 3;
while (A[r][c] != k && time <= 100) {
if (R >= C) {
int max = 0;
for (int i = 0; i < R; i++) {
int count[] = new int[101];
for (int j = 0; j < C; j++) {
count[A[i][j]]++;
}
int l = 0;
for (int j = 1; j <= C && l < 100; j++) {
for (int z = 1; z < 101; z++) {
if (count[z] == j) {
A[i][l++] = z;
A[i][l++] = j;
}
}
}
for (int j = l; j <= C && j < 100; j++) {
A[i][j] = 0;
}
max = l > max ? l : max;
}
C = max;
} else {
int max = 0;
for (int j = 0; j < C; j++) {
int count[] = new int[101];
for (int i = 0; i < R; i++) {
count[A[i][j]]++;
}
int l = 0;
for (int i = 1; i <= R; i++) {
for (int z = 1; z < 101; z++) {
if (count[z] == i) {
A[l++][j] = z;
A[l++][j] = i;
}
}
}
for (int i = l; i <= R && i < 100; i++) {
A[i][j] = 0;
}
max = l > max ? l : max;
}
R = max;
}
time++;
}
System.out.println(time > 100 ? -1 : time);
}
}복잡도
- 시간: O(100 * 100 * 100) — 최대 100번 반복, 각 반복에서 최대 100행×100열 처리
- 공간: O(100 * 100) — 배열 A 고정 크기