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

1. 문제

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

2. 접근방법

R연산과 C연산을 어떻게 풀어가느냐가 중요한 문제

연산을 하면 각 숫자의 갯수를 세고

갯수가 적으면서 숫자가 작은 순으로 정렬한 상태로

숫자 , 숫자갯수 , 숫자, 숫자갯수, ...

식으로 배열에 다시 집어 넣어줘야한다.

 

해야 하는일이

1. 숫자의 갯수를 세기

2. 세어진 숫자들로 다시 배열 조립하기

인데

 

처음에 2가지 일을 한번에 할 방법이 없을까 하다가 삽질 좀 하고

 

두가지 일을 한번에 할 수는 없구나! 를 깨달았다.

 

그래서 숫자의 갯수를 셀 때는 배열에 +1씩 해가면서 세고

모든 배열을 돌 필요 없도록

HashSet을 이용해 등장했던 숫자들을 저장한 뒤

 

HashSet에서 수를 꺼내고 배열에서 갯수를 꺼낸뒤 하나의 변수에 담아

Priority Queue에 저장한 뒤

 

pq에서 하나씩 뽑아 배열을 다시 조립하여 주었다.

 

그리고 100회까지는 검사를 하여야 한다는 점도 주의하자.

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class G4_17140이차원배열과연산 {
	static int r, c, k;
	static int rlen = 3, clen = 3;
	static int map[][] = new int[100][100];
	static TreeMap<Integer, Integer> numcnt;
	static int cntarr[] = new int[101];
	static class Point implements Comparable<Point> {
		int key;
		int value;
		
		public Point(int key, int value) {
			this.key = key;
			this.value = value;
		}

		@Override
		public int compareTo(Point o) {
			if(this.value == o.value) {
				return this.key - o.key;
			}	
			return this.value - o.value;
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken())-1;
		c = Integer.parseInt(st.nextToken())-1;
		k = Integer.parseInt(st.nextToken());
		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());
			}
		}
		int cycle = 0;
		boolean flag = false;
		while (cycle++ <= 100) {
			if(map[r][c] == k) {
				flag = true;
				break;
			}
			if (rlen >= clen)
				R();
			else
				C();
		}
		System.out.println(flag?cycle-1 : -1);
	}

	static void R() {
		int maxidx = 0;
		for (int i = 0; i < rlen; i++) {
			HashSet<Integer> set = new HashSet<>();
			PriorityQueue<Point> pq = new PriorityQueue<>();
			cntarr = new int[101];
			for (int j = 0; j < clen; j++) {
				if(map[i][j] == 0)
					continue;
				cntarr[map[i][j]]++;
				set.add(map[i][j]);
				map[i][j] = 0;
			}
			for(int k : set)
				pq.add(new Point(k,cntarr[k]));
			int idx = 0;
			while(!pq.isEmpty() && idx < 100) {
				Point now = pq.poll();
				map[i][idx] = now.key;
				if(idx+1 >= 100)
					break;
				map[i][idx+1] = now.value;
				idx +=2;
				
			}
			maxidx = Math.max(maxidx, idx);
		}
		clen = maxidx;
	}

	static void C() {
		int maxidx = 0;
		for (int j = 0; j < clen; j++) {
			HashSet<Integer> set = new HashSet<>();
			PriorityQueue<Point> pq = new PriorityQueue<>();
			cntarr = new int[101];
			for (int i = 0; i < rlen; i++) {
				if(map[i][j] == 0)
					continue;
				cntarr[map[i][j]]++;
				set.add(map[i][j]);
				map[i][j] = 0;
			}
			
			for(int k : set)
				pq.add(new Point(k,cntarr[k]));
			int idx = 0;
			while(!pq.isEmpty()  && idx < 100) {
				Point now = pq.poll();
				map[idx][j] = now.key;
				if(idx+1 >= 100)
					break;
				map[idx+1][j] = now.value;
				idx +=2;
			}
			maxidx = Math.max(maxidx, idx);
		}
		rlen = maxidx;

	}

}

4. 마치며

두 가지일을 한번에 처리하지 못할까 고민하느라 시간이 많이 든 문제였다.