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

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

17140번: 이차원 배열과 연산

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

www.acmicpc.net

풀이

연산을 계속하면서 배열 arr과 행의 크기와 열의 크기가 변하고, 배열 arr의 크기는 100을 넘어갈 수 없으므로, 100x100 크기의 arr 배열과 rSize, cSize 전역 변수를 선언한다.

또한 정렬을 수행할 때, 각각의 수가 몇 번 나왔는지 파악하여 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬해야 하기 때문에 Data라는 자료구조를 선언하여 이후 정렬을 수행할 때 사용하도록 한다.

	static class Data implements Comparable<Data> {
		int num;
		int cnt;
		
		public Data(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		
		@Override
		public int compareTo(Data o) {
			if (this.cnt == o.cnt) {
				return this.num - o.num;
			}
			return this.cnt - o.cnt;
		}
	}
    
	static int[][] arr = new int[100][100];
	static int rSize = 3, cSize = 3;

main()

- 3x3 크기의 배열 값을 입력받는다.

- 100초가 지나거나 arr[r][c] == k일 때까지 아래 작업을 반복한다.

- rSize >= cSize이면 R연산, 아니면 C 연산을 수행한다.

- arr[r][c] == k이면 시간을 출력하고 아니면 -1을 출력한다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = Integer.parseInt(st.nextToken()) - 1;
    	int c = Integer.parseInt(st.nextToken()) - 1;
    	int k = Integer.parseInt(st.nextToken());
    	
    	for (int i = 0; i < 3; i++) {
    		st = new StringTokenizer(br.readLine());
    		for (int j = 0; j < 3; j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	int time = 0;
    	while (time <= 100) {
    		if (arr[r][c] == k) break;
    		
    		if (rSize >= cSize) rFunc();
        	else cFunc();
    		
    		time++;
    	}
    	
    	if (arr[r][c] == k) bw.write(time+"");
    	else bw.write("-1");
        
        bw.flush();
        br.close();
        bw.close();
    }

void rFunc(): R 연산을 수행하는 메서드

각각의 행에 대해 다음을 수행한다.

- Map을 사용해 (숫자, 나온 횟수)를 저장한다.

- ArrayList<Data> list를 생성하여 map에 저장되어있는 (숫자, 나온 횟수)를 new Data(숫자, 나온 횟수)로 저장한다.

- list를 정렬한다.

- arr 배열에 list에 저장된 순서대로 값을 변경하고, 100개까지만 저장한다. 100개보다 적다면, 뒤에 있는 숫자들은 모두 0으로 초기화한다.

- 각 행마다의 열 크기의 최댓값을 구하여 cSize에 저장한다.

C 연산도 마찬가지로 작성한다.

	static class Data implements Comparable<Data> {
		int num;
		int cnt;
		
		public Data(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		
		@Override
		public int compareTo(Data o) {
			if (this.cnt == o.cnt) {
				return this.num - o.num;
			}
			return this.cnt - o.cnt;
		}
	}

    static void rFunc() {
    	int maxCsize = 0;
    	
    	for (int i = 0; i < rSize; i++) {
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int j = 0; j < cSize; j++) {
    			if (arr[i][j] == 0) continue;
    			
    			map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
    		}
    		
    		ArrayList<Data> list = new ArrayList<>();
    		for (int key: map.keySet()) {
    			list.add(new Data(key, map.get(key)));
    		}
    		Collections.sort(list);
    		
    		int idx = 0;
    		for (Data d: list) {
    			if (idx >= 100) break; // 100에서 짜르기
    			
    			arr[i][idx] = d.num;
    			arr[i][idx+1] = d.cnt;
    			idx += 2;
    		}
    		
    		maxCsize = Math.max(maxCsize, idx);
    		
    		for (; idx < 100; idx++) { // 뒷 부분 모두 0으로 초기화
    			arr[i][idx] = 0;
    		}
    	}
    	
    	cSize = maxCsize;
    }

시간복잡도
0 <= T <= 100
1 <= N <= 100
T * (n*(n + n + nlogn + n)) => O(T * (n^2)logn) => (10^6)log100
시간제한이 0.5초여도 통과가 되는 듯 하다.

코드

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

public class Main {
	
	static class Data implements Comparable<Data> {
		int num;
		int cnt;
		
		public Data(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		
		@Override
		public int compareTo(Data o) {
			if (this.cnt == o.cnt) {
				return this.num - o.num;
			}
			return this.cnt - o.cnt;
		}
	}
    
	static int[][] arr = new int[100][100];
	static int rSize = 3, cSize = 3;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = Integer.parseInt(st.nextToken()) - 1;
    	int c = Integer.parseInt(st.nextToken()) - 1;
    	int k = Integer.parseInt(st.nextToken());
    	
    	for (int i = 0; i < 3; i++) {
    		st = new StringTokenizer(br.readLine());
    		for (int j = 0; j < 3; j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	int time = 0;
    	while (time <= 100) {
    		if (arr[r][c] == k) break;
    		
    		if (rSize >= cSize) rFunc();
        	else cFunc();
    		
    		time++;
    	}
    	
    	if (arr[r][c] == k) bw.write(time+"");
    	else bw.write("-1");
        
        bw.flush();
        br.close();
        bw.close();
    }
    
    static void rFunc() {
    	int maxCsize = 0;
    	
    	for (int i = 0; i < rSize; i++) {
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int j = 0; j < cSize; j++) {
    			if (arr[i][j] == 0) continue;
    			
    			map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
    		}
    		
    		ArrayList<Data> list = new ArrayList<>();
    		for (int key: map.keySet()) {
    			list.add(new Data(key, map.get(key)));
    		}
    		Collections.sort(list);
    		
    		int idx = 0;
    		for (Data d: list) {
    			if (idx >= 100) break; // 100에서 짜르기
    			
    			arr[i][idx] = d.num;
    			arr[i][idx+1] = d.cnt;
    			idx += 2;
    		}
    		
    		maxCsize = Math.max(maxCsize, idx);
    		
    		for (; idx < 100; idx++) { // 뒷 부분 모두 0으로 초기화
    			arr[i][idx] = 0;
    		}
    	}
    	
    	cSize = maxCsize;
    }
    
    static void cFunc() {
    	int maxRsize = 0;
    	
    	for (int j = 0; j < cSize; j++) {
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int i = 0; i < rSize; i++) {
    			if (arr[i][j] == 0) continue;
    			
    			map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
    		}
    		
    		ArrayList<Data> list = new ArrayList<>();
    		for (int key: map.keySet()) {
    			list.add(new Data(key, map.get(key)));
    		}
    		Collections.sort(list);
    		
    		int idx = 0;
    		for (Data d: list) {
    			if (idx >= 100) break; // 100에서 짜르기
    			
    			arr[idx][j] = d.num;
    			arr[idx+1][j] = d.cnt;
    			idx += 2;
    		}
    		
    		maxRsize = Math.max(maxRsize, idx);
    		
    		for (; idx < 100; idx++) { // 뒷 부분 모두 0으로 초기화
    			arr[idx][j] = 0;
    		}
    	}
    	
    	rSize = maxRsize;
    }
}

List 대신 우선순위 큐를 사용한 풀이

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

public class Main {
	
	static class Data implements Comparable<Data> {
		int num;
		int cnt;
		
		public Data(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		
		@Override
		public int compareTo(Data o) {
			if (this.cnt == o.cnt) {
				return this.num - o.num;
			}
			return this.cnt - o.cnt;
		}
	}
    
	static int[][] arr = new int[100][100];
	static int rSize = 3, cSize = 3;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = Integer.parseInt(st.nextToken()) - 1;
    	int c = Integer.parseInt(st.nextToken()) - 1;
    	int k = Integer.parseInt(st.nextToken());
    	
    	for (int i = 0; i < 3; i++) {
    		st = new StringTokenizer(br.readLine());
    		for (int j = 0; j < 3; j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	int time = 0;
    	while (time <= 100) {
    		if (arr[r][c] == k) break;
    		
    		if (rSize >= cSize) rFunc();
        	else cFunc();
    		
    		time++;
    	}
    	
    	if (arr[r][c] == k) bw.write(time+"");
    	else bw.write("-1");
        
        bw.flush();
        br.close();
        bw.close();
    }
    
    static void rFunc() {
    	int maxCsize = 0;
    	
    	for (int i = 0; i < rSize; i++) {
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int j = 0; j < cSize; j++) {
    			if (arr[i][j] == 0) continue;
    			
    			map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
    		}
    		
    		PriorityQueue<Data> pq = new PriorityQueue<>();
    		for (int key: map.keySet()) {
    			pq.add(new Data(key, map.get(key)));
    		}
    		
    		int idx = 0;
    		while (!pq.isEmpty()) {
    			if (idx >= 100) break; // 100에서 짜르기
    			
    			Data d = pq.poll();
    			arr[i][idx] = d.num;
    			arr[i][idx+1] = d.cnt;
    			idx += 2;
    		}
    		
    		maxCsize = Math.max(maxCsize, idx);
    		
    		for (; idx < 100; idx++) { // 뒷 부분 모두 0으로 초기화
    			arr[i][idx] = 0;
    		}
    	}
    	
    	cSize = maxCsize;
    }
    
    static void cFunc() {
    	int maxRsize = 0;
    	
    	for (int j = 0; j < cSize; j++) {
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int i = 0; i < rSize; i++) {
    			if (arr[i][j] == 0) continue;
    			
    			map.put(arr[i][j], map.getOrDefault(arr[i][j], 0)+1);
    		}
    		
    		PriorityQueue<Data> pq = new PriorityQueue<>();
    		for (int key: map.keySet()) {
    			pq.add(new Data(key, map.get(key)));
    		}
    		
    		int idx = 0;
    		while (!pq.isEmpty()) {
    			if (idx >= 100) break; // 100에서 짜르기
    			
    			Data d = pq.poll();
    			arr[idx][j] = d.num;
    			arr[idx+1][j] = d.cnt;
    			idx += 2;
    		}
    		
    		maxRsize = Math.max(maxRsize, idx);
    		
    		for (; idx < 100; idx++) { // 뒷 부분 모두 0으로 초기화
    			arr[idx][j] = 0;
    		}
    	}
    	
    	rSize = maxRsize;
    }
}

728x90

'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글

[백준] 1916번 : 최소비용 구하기(다익스트라) - 자바[Java] (0)	2023.10.04
[백준] 15683번 : 감시 - 자바[Java] (0)	2023.10.04
[백준] 17276번 : 배열 돌리기 - 자바[Java] (0)	2023.10.01
[백준] 14891번 : 톱니바퀴 - 자바[Java] (0)	2023.09.25
[백준] 17144번 : 미세먼지 안녕! - 자바[Java] (0)	2023.08.16

풀이

코드

List 대신 우선순위 큐를 사용한 풀이

'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글

검색 태그

티스토리툴바