BOJ 17140
2021-01-28
위 문제는 백준 사이트의 알고리즘 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초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class BOJ17140이차원배열과연산 {
static int R;
static int C;
static int K;
static int answer = 0;
static int[][] map;
static ArrayList<Number> list;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[3][3]; // 크기가 3 x 3
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
while (true) {
if (answer > 100) { // 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
answer = -1;
break;
}
if (R - 1 < map.length && C - 1 < map[0].length) {// 끝자락에 도착했을때
if (map[R - 1][C - 1] == K) {//값이 K인가?
break;
}
}
if (map.length >= map[0].length) {//행보다 열이 크거나 같으면 R연산
rowOperation();
} else {//작다면 C연산
columnOperation();
}
answer++;
}
System.out.println(answer);
}
static void rowOperation() {
int[][] temp = new int[101][101];
int MAX = Integer.MIN_VALUE;
for (int i = 0; i < map.length; i++) {
int[] count = new int[101];
list = new ArrayList<>();
for (int j = 0; j < map[0].length; j++) { //현재있는 숫자들의 갯수를 계산
if (map[i][j] != 0) {
count[map[i][j]]++;
}
}
for (int j = 1; j < count.length; j++) { // 숫자들의 갯수를 넣어 줌.
if (count[j] != 0) {
list.add(new Number(j, count[j]));
}
}
Collections.sort(list); // Number 객체 정렬
int z = 0;
for (int j = 0; j < list.size(); j++) { // 사이즈만큼 반복한다.
temp[i][z] = list.get(j).num;// list에 있는 하나씩 temp에 꺼낸다.
temp[i][z + 1] = list.get(j).count; // 갯수도 temp에다가 넣어준다.
z += 2;// 숫자와 갯수가 들어가기 때문에 z인덱스는 2씩 늘린다.
MAX = Math.max(z, MAX);//사이즈의 최대갯수를 고려하자.
}
}
// 행이나 열이 100이 넘는 경우
if (MAX > 100) {
MAX = 100;
}
map = new int[map.length][MAX];
for (int i = 0; i < map.length; i++) {//값들을 하나씩 옮겨주자.
for (int j = 0; j < map[0].length; j++) {
map[i][j] = temp[i][j];
}
}
}
static void columnOperation() {
int[][] temp = new int[101][101];
int MAX = Integer.MIN_VALUE;
for (int i = 0; i < map[0].length; i++) {
int[] count = new int[101];
list = new ArrayList<>();
for (int j = 0; j < map.length; j++) {//현재있는 숫자들의 갯수를 계산
if (map[j][i] != 0) {
count[map[j][i]]++;
}
}
for (int j = 1; j < count.length; j++) {// 숫자들의 갯수를 넣어 줌.
if (count[j] != 0) {
list.add(new Number(j, count[j]));
}
}
Collections.sort(list); // Number 객체 정렬
int z = 0;
for (int j = 0; j < list.size(); j++) {//전체적인 틀은 rowOperation과 동일하나 x와 y쪽의 바뀜을 고려.
temp[z][i] = list.get(j).num;
temp[z + 1][i] = list.get(j).count;
z += 2;
MAX = Math.max(z, MAX);
}
}
// 행이나 열이 100이 넘는 경우
if (MAX > 100) {
MAX = 100;
}
map = new int[MAX][map[0].length];
for (int i = 0; i < map.length; i++) {//맵옮기기
for (int j = 0; j < map[0].length; j++) {
map[i][j] = temp[i][j];
}
}
}
static class Number implements Comparable<Number> {
int num;
int count;
public Number(int num, int count) {
this.num = num;
this.count = count;
}
@Override
public int compareTo(Number o) { // 정렬 조건
if (this.count > o.count) { // 갯수가 더 많은 경우 오름차순을 한다.
return 1;
} else if (this.count == o.count) { // 만약 갯수가 같다면?
if (this.num > o.num) { // 같으면서 수가 큰경우 오름차순.
return 1;
} else {
return -1;// 같으면서 수 작다면 내림차순.
}
} else {//갯수가 적다면 내림차순
return -1;
}
}
}
}
이번 문제는 시뮬레이션 문제 였습니다.
static class Number implements Comparable<Number> {
int num;
int count;
public Number(int num, int count) {
this.num = num;
this.count = count;
}
@Override
public int compareTo(Number o) { // 정렬 조건
if (this.count > o.count) { // 갯수가 더 많은 경우 오름차순을 한다.
return 1;
} else if (this.count == o.count) { // 만약 갯수가 같다면?
if (this.num > o.num) { // 같으면서 수가 큰경우 오름차순.
return 1;
} else {
return -1;// 같으면서 수 작다면 내림차순.
}
} else {//갯수가 적다면 내림차순
return -1;
}
}
}
Number 클래스에 Comparable을 이용해서 정렬조건을 정합니다.
static int R;
static int C;
static int K;
static int answer = 0;
static int[][] map;
static ArrayList<Number> list;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[3][3]; // 크기가 3 x 3
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
while (true) {
if (answer > 100) { // 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.
answer = -1;
break;
}
if (R - 1 < map.length && C - 1 < map[0].length) {// 끝자락에 도착했을때
if (map[R - 1][C - 1] == K) {//값이 K인가?
break;
}
}
if (map.length >= map[0].length) {//행보다 열이 크거나 같으면 R연산
rowOperation();
} else {//작다면 C연산
columnOperation();
}
answer++;
}
System.out.println(answer);
}
입력부입니다.
이후 조건문을 통해
- 100초가 지나면 -1출력
- 만약 끝자락에 도착했을 때 K면 빠져 나오기.
- RowOperation 과 ColumnOperation의 조건을 정합니다.
static void rowOperation() {
int[][] temp = new int[101][101];
int MAX = Integer.MIN_VALUE;
for (int i = 0; i < map.length; i++) {
int[] count = new int[101];
list = new ArrayList<>();
for (int j = 0; j < map[0].length; j++) { //현재있는 숫자들의 갯수를 계산
if (map[i][j] != 0) {
count[map[i][j]]++;
}
}
for (int j = 1; j < count.length; j++) { // 숫자들의 갯수를 넣어 줌.
if (count[j] != 0) {
list.add(new Number(j, count[j]));
}
}
Collections.sort(list); // Number 객체 정렬
int z = 0;
for (int j = 0; j < list.size(); j++) { // 사이즈만큼 반복한다.
temp[i][z] = list.get(j).num;// list에 있는 하나씩 temp에 꺼낸다.
temp[i][z + 1] = list.get(j).count; // 갯수도 temp에다가 넣어준다.
z += 2;// 숫자와 갯수가 들어가기 때문에 z인덱스는 2씩 늘린다.
MAX = Math.max(z, MAX);//사이즈의 최대갯수를 고려하자.
}
}
// 행이나 열이 100이 넘는 경우
if (MAX > 100) {
MAX = 100;
}
map = new int[map.length][MAX];
for (int i = 0; i < map.length; i++) {//값들을 하나씩 옮겨주자.
for (int j = 0; j < map[0].length; j++) {
map[i][j] = temp[i][j];
}
}
}
연산에 사용되는 알고리즘은 주석으로 첨가해 두었습니다.