[백준] G4 17140 이차원 배열과 연산 (java)

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

17140번: 이차원 배열과 연산

 

풀이

 

0) 준비물

• 해당 숫자가 몇개가 있는지 저장할 클래스 Num을 생성. 우선순위는 갯수의 오름차순 > 숫자의 오름차순
• 행과 열을 담을 Num 배열 리스트 rows[], cols[]
• 입력 받은 A배열을 담을 map[][]
• 행을 기반으로 정렬하는 sortByRow() 함수와 열을 기반으로 정렬하는 sortByCol() 함수를 생성한다.

 

1) 100 초가 지나도 답이 안나오면 -1을 출력한다 <- 100 번 반복 (while)

2) map[r][c] == k 면 반복문을 탈출하고 반복횟수를 출력한다.

3) 행>=열 이면 sortByRow() 그렇지 않다면 sortByCol()을 적용시켜 map을 갱신한다.

4) 반목문이 끝나도 2)에서 걸리지 않다면 -1

 

주의사항

 

1) 행과 열은 100보다 커질 수 없음

2) 100번째 답이나올 경우를 따져야함

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_G4_17140_이차원배열과연산 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int r,c,k,N,M, map[][];
	static List<Num> rows[], cols[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		r = Integer.parseInt(tokens.nextToken())-1;
		c = Integer.parseInt(tokens.nextToken())-1;
		k = Integer.parseInt(tokens.nextToken());
		N = 3;
		M = 3;
		map = new int[N][M];
		
		for(int i=0; i<3; i++) {
			tokens = new StringTokenizer(input.readLine());
			for(int j=0; j<3; j++) {
				map[i][j] = Integer.parseInt(tokens.nextToken());
			}	
		}
		int t = 0;
		while(t<=100) {
			if(r<N && c<M && map[r][c] == k) {
				break;
			}
			if(map.length >= map[0].length) {
				sortByRow();
			}else {
				sortByCol();
			}
			t++;
		}
		if(t <= 100) {
			System.out.println(t);
		}else {
			System.out.println(-1);
		}
	}
	private static void sortByRow() {
		int max = 0;
		rows = new List[N];
		for(int i=0; i<N; i++) {
			rows[i] = new ArrayList<>();
		}
		for(int r=0; r<N; r++) {
			for(int c=0; c<M; c++) {
				if(map[r][c] == 0) continue; // 0은 취급안함
				boolean flag = false;
				for(int i=0; i<rows[r].size(); i++) {
					if(rows[r].get(i).num == map[r][c]){
						rows[r].get(i).cnt++;
						flag = true;
						break;
					}
				}
				if(!flag) {
					rows[r].add(new Num(map[r][c], 1));
				}
			}
			Collections.sort(rows[r]);
			if(rows[r].size() > max) {
				max = rows[r].size();
			}
		}
		M = max*2;
		if(M > 100) {
			M = 100;
		}
		map = new int[N][M];
		for(int r=0; r<N; r++) {
			int cnt = 0;
			for(int c=0; c<rows[r].size(); c++) {
				map[r][cnt++] = rows[r].get(c).num;
				map[r][cnt++] = rows[r].get(c).cnt;
				if(c==49) break; // 49 맞나? 
			}
		}
	}
	private static void sortByCol() {
		int max = 0;
		cols = new List[M];
		for(int i=0; i<M; i++) {
			cols[i] = new ArrayList<>();
		}
		for(int c=0; c<M; c++) {
			for(int r=0; r<N; r++) {
				if(map[r][c] == 0) continue; // 0은 취급안함
				boolean flag = false;
				for(int i=0; i<cols[c].size(); i++) {
					if(cols[c].get(i).num == map[r][c]){
						cols[c].get(i).cnt++;
						flag = true;
						break;
					}
				}
				if(!flag) {
					cols[c].add(new Num(map[r][c], 1));
				}
			}
			Collections.sort(cols[c]);
			if(cols[c].size() > max) {
				max = cols[c].size();
			}
		}
		N = max*2;
		if(N > 100) {
			N = 100;
		}
		map = new int[N][M];
		for(int c=0; c<M; c++) {
			int cnt = 0;
			for(int r=0; r<cols[c].size(); r++) {
				map[cnt++][c] = cols[c].get(r).num;
				map[cnt++][c] = cols[c].get(r).cnt;
				if(r==49) break; // 49 맞나? 
			}
		}
	}
	static class Num implements Comparable<Num>{
		int num;
		int cnt;
		public Num(int num, int cnt) {
			super();
			this.num = num;
			this.cnt = cnt;
		}
		@Override
		public String toString() {
			return "Num [num=" + num + ", cnt=" + cnt + "]";
		}
		@Override
		public int compareTo(Num o) {
			if(this.cnt == o.cnt) {
				return Integer.compare(this.num, o.num);
			}
			return Integer.compare(this.cnt, o.cnt);
		}
	}
	static String src =
			"1 2 5\r\n" + 
			"1 2 1\r\n" + 
			"2 1 3\r\n" + 
			"3 3 3";
}

 

후기

 

 이 문제도 출제자의 악의를 느낄 수 있는 문제이다. 경계값을 잘 따져야한다.

문제를 풀다 보니 뭔가 골드4의 기준은 기존 골드5 정도의 난이도에서 정렬 같은 개념이 들어가는 정도인것 같다는 생각이 들었다.