1. 문제
설명
크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.
- R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
- C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.
예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.
정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.
행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.
입력
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)
둘째 줄부터 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차원 배열만 선언해서 문제의 복잡도를 줄였습니다.
만약 이 조건이 없었다면 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();
}
}