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

 

 

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

문제 출처 : 링크

17140번: 이차원 배열과 연산

 

올해 삼성 상반기 오후 기출 문제다.

 

처음에 글만 보고 문제를 이해하기 힘들었는데 테스트케이스 밑에 자세한 설명이 나와있었다.

 

실제로 역량테스트를 볼 때는 너무너무 자세한 예시가 나와있으니 문제 이해를 못할 걱정은 크게 걱정하지 않아두 된다ㅎㅎ

 

이처럼 행과 열의 사이즈를 비교해 숫자의 수만큼 배열을 확장해나가는 방식이다.

 

행의 길이가 열보다 더 크거나 같으면 → 방향으로

열의 길이가 행보다 더 크면 ↓ 방향으로 진행된다.

 

전체적인 while문을 돌면서, 원하는 값이 나왔을 때 진행한 횟수를 출력해주면 된다.

(이때 100번을 돌아도 답이 나오지 않으면 -1로 나오도록 해야함)

 

매 while문마다 row와 col 사이즈를 체크해서 R연산을 할지 C연산을 할지 조건문을 나누어 진행했다.

 

숫자는 cnt 배열을 만들어 인덱스를 수로 활용했고, 개수를 세고 ArrayList에 저장한 후 Sort를 통해 개수가 작은 것부터, 같으면 숫자가 작은 순으로 정렬시켰다.

 

처음에 고민했던 부분은, 배열의 사이즈는 정해져있는데 진행할 때마다 가장 큰 길이가 나오는 배열에 맞춰서 만들지에 대한 것이었다. 이는 100을 벗어날 수 없다는 문제의 조건을 활용해 temp 2차원 배열을 101크기로 만들어 놓고, 저장해서 다시 빼오는 식으로 해결할 수 있었다.

 

이처럼 배열의 사이즈를 수정하기 힘들 때는, 문제에 주어진 조건 크기만큼 temp 배열을 따로 만들어 저장하고 나중에 다시 가져오는 방법을 활용하도록 하자~

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main_17140_이차원배열과연산 {
 
    static class Num implements Comparable<Num> {
        int n;
        int len;
        
        Num(int n, int len) {
            this.n = n;
            this.len = len;
        }
 
        @Override
        public int compareTo(Num o) {
            if(this.len == o.len) {
                return this.n < o.n ? -1 : 1;
            }
            return this.len < o.len ? -1 : 1;
        }
        
        
    }
    
    static int[][] map;
    static int[] cnt;
    static ArrayList<Num> list;
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int r = Integer.parseInt(st.nextToken()) - 1;
        int c = Integer.parseInt(st.nextToken()) - 1;
        int val = Integer.parseInt(st.nextToken());
        
        map = new int[3][3];
        
        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 time = -1;
        
        while(true) {
            time++;
            
            
            if(time > 100) { // 100 넘어가면 -1
                time = -1;
                break;
            }
            
            if(r < map.length && c < map[0].length){
                if(map[r][c] == val) // 반복문 종료조건
                    break;
            }
            
            int row = map.length;
            int col = map[0].length;
            
            int[][] temp = new int[101][101];
            
            if(row >= col) { // R 연산
                
                int max = Integer.MIN_VALUE;
                
                for (int i = 0; i < row; i++) {
                    
                    cnt = new int[101];
                    for (int j = 0; j < col; j++) {
                        if(map[i][j] == 0) continue;
                        int n = map[i][j];
                        cnt[n]++;
                    }
                    
                    list = new ArrayList<>();
                    
                    for (int j = 1; j < cnt.length; j++) {
                        if(cnt[j] != 0){
                            list.add(new Num(j, cnt[j]));
                        }
                    }
                    
                    Collections.sort(list);
                    
                    int z = 0;
                    for (int j = 0; j < list.size(); j++) {
                        temp[i][z] = list.get(j).n;
                        temp[i][z+1] = list.get(j).len;
                        z+=2;
                    }
                    
                    if(max < list.size()*2) max = list.size()*2;
                    
                }
                if(max > 100) max = 100;
                
                map = new int[row][max];
                
                for (int i = 0; i < map.length; i++) {
                    for (int j = 0; j < map[i].length; j++) {
                        map[i][j] = temp[i][j];
                    }
                }
                
            }
            
            else { // C 연산
                
                int max = Integer.MIN_VALUE;
                
                for (int i = 0; i < col; i++) {
                    
                    cnt = new int[101];
                    for (int j = 0; j < row; j++) {
                        if(map[j][i] == 0) continue;
                        int n = map[j][i];
                        cnt[n]++;
                    }
                    
                    list = new ArrayList<>();
                    
                    for (int j = 1; j < cnt.length; j++) {
                        if(cnt[j] != 0){
                            list.add(new Num(j, cnt[j]));
                        }
                    }
                    
                    Collections.sort(list);
                    
                    int z = 0;
                    for (int j = 0; j < list.size(); j++) {
                        temp[z][i] = list.get(j).n;
                        temp[z+1][i] = list.get(j).len;
                        z+=2;
                    }
                    
                    if(max < list.size()*2) max = list.size()*2;
                }
                
                if(max > 100) max = 100;
                
                map = new int[max][col];
                
                for (int i = 0; i < map.length; i++) {
                    for (int j = 0; j < map[i].length; j++) {
                        map[i][j] = temp[i][j];
                    }
                }
                
            }
            
            /*System.out.println("------------------------");
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[i].length; j++) {
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("------------------------");*/
        }
        
        System.out.println(time);
    }
 
}