[백준] 17140번 이차원 배열과 연산 (java, 구현, 시뮬레이션)

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

최대 길이가 100만 가능하므로 미리 크기 100으로 만들어놓고 넘어가는 길이의 데이터만 무시해준다.

각 행별로 각 수를 count배열에 등장하는 만큼 1로 더해줘서 (수, 등장횟수) 쌍을 리스트에 넣어준다. 리스트에 넣어줄 때 중복된 수가 들어가지않도록 주의! 해준다

리스트를 기준에 따라 정렬한다.

 

최대 행 길이와 최대 열 길이는 정렬할 때마다 새로 구해줘야된다.

계속 max연산만 하면 이전 정렬에서 계산한 최대 길이보다 지금의 최대 길이가 더 작을 수도 있다. 

map을 복사한 copy배열에 새로 계산한 리스트를 다시 넣어주고 기존 map을 덮어씌워준다.

 

package algo0421;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Pair implements Comparable<Pair>{
	int num;
	int count;
	public Pair(int num, int count) {
		super();
		this.num = num;
		this.count = count;
	}
	@Override
	public int compareTo(Pair o) {
		if(this.count==o.count) {
			return this.num-o.num;
		}else {
			return this.count-o.count;
		}
	}
	
}

public class B_17140_이차원배열관연산_Main {
	static int[][] map=new int[100][100];
	static int r,c,k;
	static int rlen,clen;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		r=sc.nextInt()-1;
		c=sc.nextInt()-1;
		k=sc.nextInt();
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				map[i][j]=sc.nextInt();
			}
		}
		rlen=3;
		clen=3;
		int time=0;
		if(map[r][c]==k) {
			System.out.println(0);
			return;
		}
		while(time<100) {
//			System.out.println("rlen,clen:"+rlen+","+clen);//행, 열길이 비교
			if(rlen>=clen) {
				sortR();
			}else {
				sortC();
			}
//			print();
			time+=1;
			if(map[r][c]==k) {
				System.out.println(time);
				return;
			}
		}
		System.out.println(-1);
	}
	
	
	private static void sortC() {//열 정렬 
		int[][] copy=new int[100][100]; //배열원소가 추가 (숫자, 등장횟수)
		rlen=0;
		for (int j = 0; j < clen; j++) {//각 열
			int[] count=new int[101];
			ArrayList<Pair> list=new ArrayList<>();
			
			for (int i = 0; i < 100; i++) {
				if(map[i][j]==0)continue;
				count[map[i][j]]+=1;//각 수의 개수 
			}
			
			for (int i = 0; i < 100; i++) {
				if(map[i][j]==0)continue;
				if(count[map[i][j]]>0) {
					list.add(new Pair(map[i][j],count[map[i][j]]));//배열원소가 추가 (숫자, 등장횟수)
					count[map[i][j]]=0;//중복 안되게
				}
				
			}
			rlen=Math.max(rlen, list.size()*2);//리스트길이 두 배
			if(rlen>100)rlen=100;
			Collections.sort(list);
			for (int i = 0; i <100; i+=2) {
				if(list.size()==0)break;
				copy[i][j]=list.get(0).num;
				if(i+1>=100)break;
				copy[i+1][j]=list.get(0).count;
				list.remove(0);
			}
		}
		
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				map[i][j]=copy[i][j];
			}
		}
		
	}
	private static void sortR() {
		int[][] copy=new int[100][100];
		clen=0;//새로운 행의 길이를 구한다.
		for (int i = 0; i < rlen; i++) {
			int[] count=new int[101];
//			카운트 업데이트
			ArrayList<Pair> list=new ArrayList<>();
			for (int j = 0; j < 100; j++) {
				if(map[i][j]==0)continue;
				count[map[i][j]]+=1;//각 수의 개수 
			}
			//존재하는 수면 해당 수와 등장횟수 list에 넣어줌. 중복 안되도록 count는 0으로 초기화
			for (int j = 0; j < 100; j++) {
				if(map[i][j]==0)continue;
				if(count[map[i][j]]>0) {
				list.add(new Pair(map[i][j],count[map[i][j]]));
				count[map[i][j]]=0;
				}
			}
			Collections.sort(list);// 정렬
			clen=Math.max(clen, list.size()*2);
			if(clen>=100)clen=100;
			for (int j = 0; j <100; j+=2) {
				if(list.size()==0)break;
				copy[i][j]=list.get(0).num;
				if(j+1>=100)break;
				copy[i][j+1]=list.get(0).count;
				list.remove(0);
			}

		}
		
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				map[i][j]=copy[i][j];
			}
		}
		
	}
	
	private static void print() {
		for (int i = 0; i < rlen; i++) {
			for (int j = 0; j < clen; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
}