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

문제 링크

17140번: 이차원 배열과 연산

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

 

이 문제에 핵심은

 

1. 1초마다 상황에 따른 R연산과 C연산이 진행되면서 배열의 형태가 변경됩니다.

2. 배열의 [r][c]의 값이 k가 될 때까지의 지나간 초를 결과로 출력합니다. 

3. 100초가 지나갈 때까지 종료되지 않으면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. Arr[r][c]의 값이 k가 될 때까지 상황에 맞게 R연산 및 C연산을 수행하는 시뮬레이션을 진행합니다.

 

3. 시뮬레이션이 종료 후, 지난 초를 결과로 출력합니다.

 

 

R 연산(행의 개수 ≥ 열의 개수)

 

행에 대해서 정렬을 수행한다.

1	2
3	3

숫자의 반복 횟수를 기준 오름차순 정렬

1	1	2	1
3	2	0	0

C 연산(행의 개수 ＜ 열의 개수)

 

열에 대해서 정렬을 수행한다.

1	2
3	3

숫자의 반복 횟수를 기준 오름차순 정렬

1	2
1	1
3	3
1	1

 

예제입력 2.

 

1. 입력되는 정보들을 저장합니다.

 

r : 1

c : 2

k : 1

1	2	1
2	1	3
3	3	3

2. Arr[r][c]의 값이 k가 될 때까지 상황에 맞게 R연산 및 C연산을 수행하는 시뮬레이션을 진행합니다.

 

Arr[r][c] = Arr[1][2] = 2

 

행의 개수 : 3

열의 개수 : 3

행의 개수 ≥ 열의 개수

 

R연산 수행!

2	1	1	2	0	0
1	1	2	1	3	1
3	3	0	0	0	0

 

Arr[r][c] = Arr[1][2] = 1

종료!

 

3. 시뮬레이션이 종료 후, 지난 초를 결과로 출력합니다.

 

시뮬레이션을 통해 지나간 1초를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력된 정보에 대하여 나누었습니다.
• arr[r][c]가 k가 될 때까지  cal를 실행하여 시뮬레이션을 진행합니다.
• 100초를 벗어나면 -1, 벗어나지 않으면 지나간 초를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 R연산과 C연산을 진행하여 배열을 바꿉니다.
• cal함수는 HashMap을 이용하여 숫자를 키, 반복횟수를 값으로 저장합니다.
• cal함수는 HashMap에 저장된 값들을 List에 옮겨서 정렬한 뒤 배열에 적용되도록 하였습니다.

 

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

public class Main {
    //번호, 반복횟수 관련 클래스
    static class num implements Comparable<num>{
        int n, count;
        public num(int n, int count) {
            this.n = n;
            this.count = count;
        }
        //반복횟수 오름차순, 같을 때에는 번호 오름차순 Comparable
        @Override
        public int compareTo(num o) {
            if(this.count == o.count)
                return this.n - o.n;
            else
                return this.count - o.count;
        }
    }
    static int r,c,k;
    static int[][] arr = new int[101][101];	//배열에 대한 정보 저장
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }
        bw.write(cal() + "");	//지나간 초를 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //시뮬레이션 진행하는 함수
    static int cal(){
        int time = 0;	//초
        int row = 3, col = 3;	//행의 개수, 열의 개수 저장 변수
        HashMap<Integer, Integer> map = new HashMap<>();	//숫자 중복횟수 HashMap
        ArrayList<num> list = new ArrayList<>();	//정렬하기 위한 리스트
        while(true){
            if(arr[r][c] == k )	//arr[r][c]가 k가 될 때
                break;
            if(time>100){	//100초가 벗어날 때
                time = -1;
                break;
            }
            int[][] temp = new int[101][101];
            if(row>=col){		//R연산
                for(int i=0;i<row;i++){
                    for(int j=0;j<col;j++)
                        if(arr[i][j]!=0)
                            map.put(arr[i][j], map.getOrDefault(arr[i][j],0)+1);
                    if(map.isEmpty())	//해당 행의 숫자 없는 경우
                        continue;
                    for(Integer key : map.keySet())	//숫자 반복횟수 리스트에 저장
                        list.add(new num(key, map.get(key)));
                    Collections.sort(list);		//정렬
                    col = Math.max(col, list.size()*2);	//변경된 행 사이즈 변경
                    int index = 0;
                    for(num n : list){
                        temp[i][index++] = n.n;
                        temp[i][index++] = n.count;
                    }
                    map.clear();
                    list.clear();
                }
            }else{		//C연산
                for(int i=0;i<col;i++){
                    for(int j=0;j<row;j++)
                        if(arr[j][i]!=0)
                            map.put(arr[j][i], map.getOrDefault(arr[j][i], 0)+1);
                    if(map.isEmpty())	//해당 행의 숫자 없는 경우
                        continue;
                    for(Integer key : map.keySet())	//숫자 반복횟수 리스트에 저장
                        list.add(new num(key, map.get(key)));
                    Collections.sort(list);	//정렬
                    row = Math.max(row,list.size()*2);	//변경된 열 사이즈 변경
                    int index = 0;
                    for(num n : list){
                        temp[index++][i] = n.n;
                        temp[index++][i] = n.count;
                    }
                    map.clear();
                    list.clear();
                }
            }
            arr = temp;
            time++;
        }
        return time;
    }
}