[백준] 23291 - 어항 정리

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

23291번: 어항 정리

 

 

두번째로 풀어본 플레문제!

사실 이거 플레 맞나...? 싶긴 했지만 확실히 골드 문제보다는 하라는게 많기는 했다.

그래도 메소드를 잘 분리해서 문제에 나온대로 차근차근 풀면 풀 수 있었던 문제.

3시간 걸렸는데 더 연습해서 시간을 줄여나가면 좋겠다.

 

 

풀이 방법

• 순서
  • 공중부양1(가능할때까지 반복)
  • 물고기 수 조절
  • 바닥에 일렬로 놓기
  • 공중부양2(2번)
  • 물고기 수 조절
  • 바닥에 일렬로 놓기
• 필요한 함수
  • 공중부양1
    1. 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 여러개면 모두 한 마리씩 넣는다.
       • list에 물고기 수가 min값인 어항을 넣는다
         • 현재 어항이 min보다 작으면 list를 비우고 현재 어항만 넣는다
         • 현재 어항이 min과 같으면 list에 그냥 넣는다
       • list에 있는 어항에 물고기수 +1
    2. 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올린다.
       • newFishbowls = int[2][N-1]
       • newFishbowls[1][0] = fishbowls[0]
       • newFishbowls[0][0]~[0][N-2] = fishbowls[1]~fishbowls[N-1]
    3. 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다.공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 있을때까지 3~4번 과정을 반복한다.
       • height = 2 //쌓여있는 어항 높이
       • cnt = 1 //2개 이상 쌓여있는 어항이 몇줄인지
       • floor = N-1 //바닥 어항 개수
       • 공중부양하는 어항들을 빼고 나머지 바닥 채우기
       • 공중부양해서 회전 후 어항 쌓을 바닥이 있을때만 반복
         • int[][] newFB = new int[cnt+1][floor-cnt]
         • cnt 만큼 들어올려 90도 회전해서 쌓기
       • 변수 갱신하기
         • newFishbowls = newFB
         • int temp = height
         • floor -= cnt
         • height = cnt+1
         • cnt = temp
    4. 부양시킨 어항을 바닥에 있는 어항의 왼쪽 위에 올려놓는다.
  • 물고기 수 조절
    • 어항을 정리하면 물고기의 수를 조절한다. 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다.
      1. 모든 인접한 두 어항에 대해 물고기 수의 차이/5 = d 를 구한다.
         • 각 칸에서 증감해야할 수 기록할 배열 만들기
         • (0,0)부터 시작할 경우 오른쪽, 아래쪽이랑만 비교하면 됨
      2. 두 어항 중 물고기가 많은 곳의 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다.
  • 바닥에 일렬로 놓기
    • 어항을 1행 N열부터 1행 1열, 그다음 2행 N열~1열, 3행 N열~1열… 끝까지 일렬로 바닥에 놓는다.
  • 공중부양2
    1. 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전시킨다.
    2. 오른쪽 N/2개의 위에 놓는다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_BJ_23291_어항정리{

    private static int N, K;
    private static int[] originalFishbowls;
    private static int[][] tempFishbowls;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        originalFishbowls = new int[N];
        for (int i = 0; i < N; i++) {
            originalFishbowls[i] = Integer.parseInt(st.nextToken());
        }

        int cnt=1;
        while(solve()>K) cnt++;

        System.out.println(cnt);
    }

    private static int solve() {
        levitation1();
        controlFish();
        lineUp();
        levitation2();
        levitation2();
        controlFish();
        lineUp();

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int fish : originalFishbowls) {
            max = Math.max(max, fish);
            min = Math.min(min, fish);
        }

        return max-min;
    }

    private static void levitation1() {

        //1. 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다.  여러개면 모두 한 마리씩 넣는다.
        // list에 물고기 수가 min값인 어항을 넣는다
        int min=Integer.MAX_VALUE;
        List<Integer> minList = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            //현재 어항이 min보다 작으면 list를 비우고 min 갱신한다.
            if(min > originalFishbowls[i]) {
                minList.clear();
                min = originalFishbowls[i];
            }
            //현재 어항이 min과 같으면 list에 어항index를 넣는다.
            if(min == originalFishbowls[i]) minList.add(i);
        }

        //list에 있는 어항에 물고기수 +1
        for(int index : minList) originalFishbowls[index]++;


        //2. 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올린다.
        tempFishbowls = new int[2][N-1];
        tempFishbowls[0][0] = originalFishbowls[0];
        for(int i=0; i<N-1; i++) {
            tempFishbowls[1][i] = originalFishbowls[i+1];
        }            


        //3. 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다.
        //부양시킨 어항을 바닥에 있는 어항의 왼쪽 위에 올려놓는다. 
        //공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 있을때까지 반복한다.

        int height = 2;   //쌓여있는 어항 높이
        int cnt = 1;    //2개 이상 쌓여있는 어항이 몇줄인지
        int floor = N-1;   //바닥 어항 개수

        //공중부양해서 회전 후 어항 쌓을 바닥이 있을때만 가능
        while(floor-cnt >= height) {            
            int[][] newFB = new int[cnt+1][floor-cnt];

            //바닥 채우기
//            for(int i=0; i<newFB[0].length; i++) {
//                newFB[newFB.length-1][i] = tempFishbowls[tempFishbowls.length-1][i+cnt];
//            }
            newFB[newFB.length-1] = Arrays.copyOfRange(tempFishbowls[tempFishbowls.length-1], cnt, tempFishbowls[0].length);

            //공중부양해서 90도 회전하여 위에 쌓기
            for(int i=0; i<cnt; i++) {
                for(int j=0; j<height; j++) {
                    newFB[i][height-1-j] = tempFishbowls[j][i];
                }
            }

            //변수 갱신
            tempFishbowls = newFB;
            int temp = height;
            floor -= cnt;
            height = cnt+1;
            cnt = temp;
        }
    }


    private static void controlFish() {
        // 물고기의 수를 조절한다. 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다.
        //1. 물고기 수의 차이/5 = d 를 구한다.

        int R = tempFishbowls.length;
        int C = tempFishbowls[0].length;
        //각 칸의 증감 기록할 배열
        int[][] increase = new int[R][C];

        //(0,0)부터 시작할 경우 오른쪽, 아래쪽이랑만 비교하면 됨
        int[][] delta = {{1,0},{0,1}};
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                for(int[] dir : delta) {
                    //0이면 어항 X
                    if(tempFishbowls[i][j]==0) continue;
                    int tr = i+dir[0];
                    int tc = j+dir[1];
                    if(0<=tr && tr<R && 0<=tc && tc<C && tempFishbowls[tr][tc]!=0) {
                        int d = Math.abs(tempFishbowls[i][j] - tempFishbowls[tr][tc])/5;
                        //많은 쪽에서 적은 쪽으로 d 만큼 이동하는 증감 기록
                        if(tempFishbowls[i][j] > tempFishbowls[tr][tc]) {
                            increase[i][j] += -1*d;
                            increase[tr][tc] += d;
                        }else {
                            increase[i][j] += d;
                            increase[tr][tc] += -1*d;
                        }
                    }
                }
            }
        }

        //2. 두 어항 중 물고기가 많은 곳의 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다.
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                tempFishbowls[i][j] += increase[i][j];
            }
        }
    }

    private static void lineUp() {
        //어항을 1행 R열부터 1행 1열, 그다음 2행R열~1열, 3행R열~1열… 끝까지 일렬로 바닥에 놓는다
        int R = tempFishbowls.length;
        int C = tempFishbowls[0].length;
        int cnt=0;

        int[][] newFB = new int[1][N];
        for(int j=0; j<C; j++) {
            for(int i=R-1; i>=0; i--) {
                if(tempFishbowls[i][j]!=0) {
                    newFB[0][cnt++] = tempFishbowls[i][j];
                }
            }
        }

        tempFishbowls = newFB;
        originalFishbowls = newFB[0];
    }

    private static void levitation2() {
        int R = tempFishbowls.length;
        int C = tempFishbowls[0].length;
        int[][] newFB = new int[R*2][C/2];

        //1. 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전시킨다.

        //공중부양 안하는 부분 바닥에 쌓아주기
        for(int i=1; i<=R; i++) {
            newFB[R*2-i] = Arrays.copyOfRange(tempFishbowls[R-i], C/2, C);
        }

        //공중부양해서 180도 회전하여 위에 쌓기
        for(int i=0; i<R; i++) {
            for(int j=0; j<C/2; j++) {
                newFB[i][j] = tempFishbowls[R-1-i][C/2-1-j];
            }
        }

        tempFishbowls = newFB;
    }

    private static void print(int[][] arr) {
        System.out.println();
        for(int i=0; i<arr.length; i++) {
            System.out.println(Arrays.toString(arr[i]));
        }
    }

}