[ 백준 / 17140 ] 이차원 배열과 연산 - Java

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

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

 

문제

크기가 3×3인 배열 A가 있다. 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을 넘어가는 경우에는 -1을 출력한다.

 

문제가 되게 읽기 힘들었다..

이해하는데 우선 시간이 좀 걸렸다고 생각한다.

그리고 75%? 74%에서 한번 틀렸는데, 100을 초과하는 경우와 100인경우를 잘 생각하도록 하자...

 

풀이 코드를 먼저 첨부하고 설명한다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 이차원_배열과_연산 {
	public static void main(String[] args) throws IOException {
		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[] temp = new int[100];
					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);
	}
}

 문제는 읽기에는 어렵지만 설명이 Hint로 친절하게 나와있어서 푸는 거 자체는 어렵지 않게 풀었다.

Gold 4중에서는 쉬운 문제인 거 같다. 

 

문제는 숫자의 개수를 세어 그 숫자만큼 출력하는 문제이다. 

그리고 그 배열의 크기는 총 100이 넘어서는 안된다. 

이 조건을 생각했을 떄 100을 준것에는 이유가 있을 것이라고 생각하였다. 

시간도 0.5초 이기 떄문에 ArrayList로 구현하기 보다는 배열을 최대한 크게 만들어서 푸는게 더 쉽고, 

시간도 절약할 수 있을 것이라고 생각하였다. ArrayList로 구현할 경우, C연산을 하는 경우에 어려움을 겪었다. 

 

R연산과 C연산을 통해 정렬하는 방법은 간단히 

A[i][j]값의 개수만 count배열에 있다. 

나온 숫자의 개수를 세어, 이를 나타내는 방법 이다. 앞서 예가 있듯, [1,2,1]이 있는 경우 , 1이 2개 2가 하나이므로 

작은순으로 정렬하여 [2,1, 1,2] 가 된다.

이를 구현하는 방법으로는 무식하게 배열의 개수만큼 반복을 돌면서 1~100까지 있는 변수에 개수를 count하는 방법으로 구현하였다. 이게 나중에 100개 정도 되면 더 빠르고 간단하게 구현이 가능하지만 지금 알고리즘에서는 사실 모르겠다.. 총 배열이 몇개 있는지가 중요하게 작용할 것이라고 생각한다. 

그래서 1~100까지 개수를 넣어 놓았으면, 이후에 A배열에 새로운 배열을 다시 넣어주면 된느데, 

l이라는 변수를 넣어서 현재 배열의 크기를 가질 수 있도록 하면서 ++연산을 진행한다. 

C에는 현재 배열에서 가장 큰 값이 들어있는데, 그래서 0으로 채워줘야 할 부분이 있느냐 없느냐를 검사하게 된다.

그리고 새로운 배열을 진행하면서, C값이 총 계산 이후에 바뀌게 될 것인데, 이를 위해 

max값으로 새로운 정렬에서 나타난 배열의 가장 긴 길이를 찾고, 모든 R연산을 진행한 후 C에 넣어주었다. 

C연산의 경우도 R의 연산에서 가로 세로만 변하고 동일하게 진행된다. 

그리고 마지막 연산이 완료된 이후 time 의 값을 ++해준다. 

배열을 결과가 나오거나 time이 100보다 작거나 같은 경우까지만 돌게 된다. 

 

그리고 마지막에 결과가 나왔을 경우의 time, 아니면 100을 초과했을 경우의 time을 출력해주면 문제는 풀린다.