[백준 17140] 이차원 배열과 연산 (자바)

 

 

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

17140번: 이차원 배열과 연산

난이도 : 골드 4

 

문제를 읽었을 때 한번에 이해가 되지 않아 여러 번 반복해서 읽게 되는 문제들이 있습니다.

이 문제가 저한텐 이해가 한번에 잘 되지 않았네요.

 

R연산 : 행의 길이와 열의 길이가 같을 때.

C연산 : 열의 길이가 행의 길이보다 길 때.

 

R, C연산을 할 때 기준에 맞춰서 정렬을 시작합니다. 

정렬 기준은 숫자의 등장 횟수(오름차순), 동일 횟수면 숫자(오름차순)입니다. 

즉, 각 행과 열에 대해 정렬 시 그 라인의 숫자들을 읽어 숫자와 횟수를 count 한 후

정렬 기준에 맞춰 차례대로 배열에 적어내면 됩니다.

이렇게 연산을 했을 시 문제에서 주어진 좌표에 있는 값을 비교하고 출력을 하거나 연산을 또 하면 됩니다.

 

단순하게 구현을 하는 문제라 조건만 잘 기억한다면 까다롭진 않았습니다.

R, C연산을 할 때 정렬 라인의 숫자를 세는 것은 Map을 이용했고,

이 값들을 (숫자, 횟수)의 값을 가지는 Node 클래스를 생성하여 

PirorityQueue에 넣어 정렬했습니다.

 

---

전역 변수 

r, c = 문제에서 지정한 좌표 값

k = 문제에서 원하는 좌표의 값

map[][] = 초기 배열 값xNum = 배열에서 가장 긴 행의 길이yNum = 배열에서 가장 긴 열의 길이

 

메소드

void main 

입력을 받습니다.(cal 호출)

void cal

R, C연산을 수행합니다. 연산을 수행하고 기준에 맞춰 정렬하고 배열에 값을 넣습니다.
가장 긴 행의 길이를 xNum, 가장 긴 열의 길이를 yNum에 저장하여 관리했습니다.

(clear 호출)

void clear

파라미터로 받은 라인의 인덱스와 행, 열을 구분하는 boolean 값을 통해

새로운 값을 적기 위해 그 줄을 0으로 초기화합니다.

class Node

PriorityQueue에서 정렬을 하기 위해 Comparable이 가능한 클래스를 생성합니다.

숫자와 그 숫자의 count 횟수를 가집니다.

import java.io.*;
import java.util.*;

public class p17140 {
	static int r, c, k, map[][], xNum, yNum;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		r = Integer.parseInt(stz.nextToken());
		c = Integer.parseInt(stz.nextToken());
		k = Integer.parseInt(stz.nextToken());
		xNum = 3;
		yNum = 3;
		map = new int[100][100];

		for(int i = 0; i < 3; i++) {
			stz = new StringTokenizer(br.readLine());
			for(int j = 0; j < 3; j++)
				map[i][j] = Integer.parseInt(stz.nextToken());
		}

		cal();
	}

	public static void cal() {
		int answer = 0;
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		Iterator it;

		while(map[r-1][c-1] != k) {
			if(answer == 101)
				break;

			if(xNum >= yNum) {
				for(int i = 0; i < xNum; i++) {
					hashMap.clear();
					pq.clear();

					for(int j = 0; j < yNum; j++) {
						int now = map[i][j];
						if(now == 0)
							continue;
						if(hashMap.containsKey(now))
							hashMap.put(now, hashMap.get(now)+1);
						else
							hashMap.put(now, 1);
					}
					clear(true, i);
					it = hashMap.keySet().iterator();

					while(it.hasNext()){
						int key = (int)it.next();
						pq.add(new Node(key, hashMap.get(key)));
					}

					int index = 0;
					while(!pq.isEmpty()) {
						if(index == 100)
							break;

						Node node = pq.poll();
						int number = node.number;
						int count = node.count;
						map[i][index++] = number;
						map[i][index++] = count;

						if(index > yNum)
							yNum = index;
					}
				}
			}
			else {
				for(int i = 0; i < yNum; i++) {
					hashMap.clear();
					pq.clear();

					for(int j = 0; j < xNum; j++) {
						int now = map[j][i];
						if(now == 0)
							continue;
						if(hashMap.containsKey(now))
							hashMap.put(now, hashMap.get(now)+1);
						else
							hashMap.put(now, 1);
					}
					clear(false, i);
					it = hashMap.keySet().iterator();

					while(it.hasNext()){
						int key = (int)it.next();
						pq.add(new Node(key, hashMap.get(key)));
					}

					int index = 0;
					while(!pq.isEmpty()) {
						if(index == 100)
							break;

						Node node = pq.poll();
						int number = node.number;
						int count = node.count;
						map[index++][i] = number;
						map[index++][i] = count;

						if(index > xNum)
							xNum = index;
					}
				}
			}
			answer ++;
		}
		System.out.println(answer > 100 ? -1 : answer);
	}

	public static void clear(boolean x, int line) {
		if(x) {
			for(int i = 0; i < 100; i++)
				map[line][i] = 0;
		}
		else
			for(int i = 0; i < 100; i++)
				map[i][line] = 0;
	}

	static class Node implements Comparable<Node> {
		int number;
		int count;
		Node(int number, int count) {
			this.number = number;
			this.count = count;
		}

		public int compareTo(Node o) {
			if(count == o.count)
				return number-o.number;
			return count - o.count;
		}
	}
}

 

cal 메소드가 너무 더러워서 마음에 들지 않습니다.

좀 더 다듬을 수 있게 생각해봐야겠습니다.