17140번 이차원 배열과 연산
난이도
플레티넘 4
문제 설명
https://www.acmicpc.net/problem/17140
문제
크기가 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을 출력한다.
예제 입력 1
1 2 2
1 2 1
2 1 3
3 3 3
예제 출력 1
0
예제 입력 2
1 2 1
1 2 1
2 1 3
3 3 3
예제 출력 2
1
예제 입력 3
1 2 3
1 2 1
2 1 3
3 3 3
예제 출력 3
2
요구사항
- 3x3에서 시작하는 2차원 배열에 대해 매 초마다 R, C 연산을 적용하여 A[r][c] == k가 되는 최소 시간(0~100초)을 출력한다.
- 행 개수 >= 열 개수 : R 연산
- 행 개수 < 열 개수 : C 연산
- 0은 무시하며, 각 값의 등장 횟수를 센 뒤 (횟수 오름차순, 값 오름차순) 정렬한다.
- 값, 횟수, 값, 횟수, ... 순으로 채우며 한 줄 길이를 100개까지 유지한다
- 가장 긴 행, 열의 길이에 맞춰 0으로 채운다.
접근 방식
최대 크기가 100이므로 1-index 기준 100×100 이차원 배열을 사용하였다. 메인 루프(t=0…100)에서 매 초 A[r][c] == k를 확인해 만족하면 그 시간을 반환하고, 끝까지 만족하지 못하면 -1을 반환하였다.
매 초 현재 행·열 개수를 비교해 R 또는 C 연산을 수행하였다. R/C 연산은 줄 단위로 처리하며, 0을 제외한 값들을 Map<Integer, Integer>에 집계한 뒤 등장 횟수 오름차순, 동률일 때는 값 오름차순으로 정렬한다.
정렬 결과를 num, cnt 순서로 배열에 다시 기록하고, 남은 칸은 0으로 채워 패딩하여 이전 턴의 데이터가 남지 않도록 하였다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.spec.RSAOtherPrimeInfo;
import java.util.*;
class Point implements Comparable<Point>{
int num;
int cnt;
public Point(int num, int cnt) {
this.num = num;
this.cnt = cnt;
}
@Override
public int compareTo(Point o){
if(this.cnt == o.cnt) return this.num - o.num;
else return this.cnt - o.cnt;
}
}
public class Main{
static int r, c, k;
static int xLen=3, yLen=3;
static int[][] arr = new int[101][101];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
for(int i=1; i<=3; i++){
st = new StringTokenizer(br.readLine());
for(int j=1; j<=3; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(solution());
}
static int solution(){
for(int t=0; t<=100; t++){
if(arr[r][c] == k) return t;
size();
}
return -1;
}
static void size(){
int xl = xLen; int yl = yLen;
if(xLen >= yLen) R(yl);
else C(xl);
}
static void R(int yl){
for(int i=1; i<=xLen; i++){
Map<Integer, Integer> map = new HashMap<>();
List<Point> li = new ArrayList<>();
for(int j=1; j<=yl; j++){
int key = arr[i][j];
if(key == 0) continue;
map.put(key, map.getOrDefault(key, 0)+1);
}
for(Map.Entry<Integer, Integer> e : map.entrySet()){
li.add( new Point(e.getKey(), e.getValue()));
}
Collections.sort(li);
int col = 1;
for(Point p : li){
arr[i][col++] = p.num;
arr[i][col++] = p.cnt;
}
yLen = Math.max(yLen, col);
while (col <= 100){
arr[i][col++] = 0;
}
}
}
static void C(int xl){
for(int i=1; i<=yLen; i++){
Map<Integer, Integer> map = new HashMap<>();
List<Point> li = new ArrayList<>();
for(int j=1; j<=xl; j++){
int key = arr[j][i];
if(key == 0) continue;
map.put(key, map.getOrDefault(key, 0)+1);
}
for(Map.Entry<Integer, Integer> e : map.entrySet()){
li.add( new Point(e.getKey(), e.getValue()));
}
Collections.sort(li);
int row = 1;
for(Point p : li){
arr[row++][i] = p.num;
arr[row++][i] = p.cnt;
}
xLen = Math.max(xLen, row);
while (row <= 100){
arr[row++][i] = 0;
}
}
}
}느낀점
이 문제는 알고리즘 적 구현보다는 '라인 변환 정확도' (0 무시, 빈도 정렬, 값과 횟수 순으로 쓰기, 100제한)를 정확히 구현하는 것이 핵심이였다.
빈도를 집계하기 위해 Map을 사용하였는데, Map자료형 사용법에 더욱 친숙해졌다.
처음에는 값, 횟수 순으로 한 줄을 채운 후 0으로 패딩을 채우는 과정에서 어려움을 겪었다. 하지만, 한 줄을 기록한 직후 바로 다음 칸부터 남은 구간까지 0으로 채우게 된다면, 이전의 값들도 자연스럽게 지워지고 패딩을 채울 수 있어 간단하게 구현할 수 있었다.
