[Java] 백준 18111번 : 마인크래프트

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

18111번: 마인크래프트

 

[접근] 

맨 처음에 푼 코드는 이러하다.

 

1) N X M 크기의 2차원 배열에 수를 저장하면서 최소 높이와 최대 높이를 구한다.

2) 최소높이 ~최대 높이 만큼의 반복문을 돌면서 만들어놓은 2차원 배열의 인덱스에 하나씩 접근하면서

 - 땅의 높이(2차원 배열 값) 가 기준이 되는 높이 (h) 보다 높을 경우 , 인벤토리에 블록을 넣어야하기때문에 2초를 더하고 가지고 있는 블록수도 더하여  블록값을 갱신시킨다.

- 땅의 높이(2차원 배열 값 ) 가 기준이 되는 높이 (h)보다 낮을 경우 ,  블록을 쌓아햐 하기 때문에 1초를 더하고 가지고있는 블록 수에서 차이 만큼 블록수를 빼준다.

 

3) 이렇게 연산을 다 하고 기준 층 수에서 블록수가 음수일 경우는 땅 고르기를 할 수 없으므로 (시간, 층수)를 저장하지않는다. 그렇지 않으면 저장시켜주면 된다.

 

4) 값을 저장시킬때 HashMap 을 이용하여 같은 시간에 증복된 층수가 있으면 값을 씌워주는 방법을 써보았다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); //행 수
        int M = Integer.parseInt(st.nextToken()); //열 수
        int B = Integer.parseInt(st.nextToken()); //인벤토리 블럭 수
        int [][] minecarft = new int[N][M];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); //최소 시간 , 층수

        int min_H=256; //최소 높이
        int max_H=0;   //최대 높이

        //2차 원 배열에 땅 높이를 저장시킨다.
        //땅 고르기를 할 수 있는 최소 높이와 최대 높이를 구한다.
        for (int i = 0; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j =0 ; j < M ; j++){
                    minecarft[i][j]=Integer.parseInt(st.nextToken());

                    if ( minecarft[i][j]>=max_H){ //최대 높이 구하기
                        max_H =minecarft[i][j];

                }

                    if (minecarft[i][j]<=min_H){ //최소 높이 구하기
                        min_H = minecarft[i][j];
                    }
            }
        }

        //최소 높이 부터 최대 높이까지 작업을 진행한다.
        for (int i = min_H ; i <= max_H;i++){ //i 가 땅을고를 기준인 수가 된다.
            int time =0;
            int block = B; //층이 바뀔때마다 블록수를 처음 받아온 블록 수 로 초기화

            for(int j = 0 ; j <N ; j++){ //2차원 배열 접근
                for(int k = 0 ; k <M;k++){

                    if (minecarft[j][k]==i){
                        continue;
                    }
                    if (minecarft[j][k]>i){ // 땅의 높이가 기준높이(i)보다 높을경우
                        int d = minecarft[j][k]-i;
                        block= block+ d; //차이 만큼 블럭을 증가시킨다.
                        time= time + (d*2); //블럭을 인벤토리에 넣는작업 +2초

                    }else {//땅의 높이가 기준높이 (i)보다 작을경우 블럭을 올린다.
                        int d = i-minecarft[j][k];
                        block = block -d;
                        time=time+d;
                    }
                }
            }
            // (최소 시간 , (중복이있다면 가장 큰 수) 높이 )
            // 기준 높이(i)를 기준으로,  기존블록수 (B) + 인벤토리에 넣을 수 있는 블록수 - 올려야하는블록수 가 음수보다 커야
            //땅을 고르게 할 수 있기 때문에 그때만 hashmap에 저장시킨다.
            if(block>-1) {
                map.put(time, i);
            }
        }

        int key = Collections.min(map.keySet());
        System.out.print(key+" "+map.get(key));

    }
}

[결과] 

이런식으로 풀었더니 시간이 768ms 가 나왔다. 백준 사이트에서 다른 사람의 풀이를 보았는데 , 내 코드에서는 3중 for 문이 사용되었는데 

2중 for문으로도 풀 수 있는 코드를 보게 되었다. 그 코드를 보면서 어떻게 할 수 있는지 생각해보고 2중 for문으로 다시 짜보았다.

 

- 처음 풀었던 코드와 다른점은 2차원 배열에 입력 값들을 저장시킬때 , 최대 높이(256)+1 만큼의 정수형 배열(count[])을 만들어 해당하는 인덱스 번호를 층 수로 사용하여 같은 층수가 몇개 있는지 세주는 작업을 한다. 이렇게 하면 2차원 배열을 굳이 접근해서 인벤토리에 넣어야할 블록 수나 쌓아야되는 블록 수를 구하지 않아도 된다.  불필요한 접근을 할 필요가 없게 된다. 

 

[코드 수정]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); //행 수
        int M = Integer.parseInt(st.nextToken()); //열 수
        int B = Integer.parseInt(st.nextToken()); //인벤토리 블럭 수
        int [][] minecarft = new int[N][M];
        int count [] = new int[257]; // 인덱스 번호를 층수로 활용하여 해당하는 인덱스 번호의 층수가 몇개가있는지 저장시킬것이다.

        int min_H=256; //최소 높이
        int max_H=0;   //최대 높이

        //2차 원 배열에 땅 높이를 저장시킨다.
        //땅 고르기를 할 수 있는 최소 높이와 최대 높이를 구한다.
        for (int i = 0; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j =0 ; j < M ; j++){
                    minecarft[i][j]=Integer.parseInt(st.nextToken());
                    count[minecarft[i][j]]+=1; //같은 층이 몇개있는지 인덱스 번호를 이용하여 수를 세어준다.

                    if ( minecarft[i][j]>=max_H){ //최대 높이 구하기
                        max_H =minecarft[i][j];

                }

                    if (minecarft[i][j]<=min_H){ //최소 높이 구하기
                        min_H = minecarft[i][j];
                    }
            }
        }

        int []answer = {Integer.MAX_VALUE, 257};// {시간, 높이}
        //최소 높이 부터 최대 높이까지 작업을 진행한다.
        for (int h = max_H ; h >= min_H;h--){ //i 가 땅을고를 기준인 수가 된다.
            int time =0;
            int block = B; //층이 바뀔때마다 블록수를 처음 받아온 블록 수 로 초기화

         for (int k=max_H ; k>h;k--){ //최대 층부터 기준층 전까지 내려가면서 연산
             int d = (k-h) *count[k]; //인벤토리에 넣어야할 블록수를 계산
             time+=d*2;
             block = block +d;
            }


         for (int k = min_H; k<h;k++){ //최소 층 부터 기준층 전까지 올라가면서 연산
             int d = (h-k) * count[k];//블록 위에 올려야할 블록 수를 계산
             time = time +d;
             block = block -d;
         }

         // 전부 계산 후 블록수가 음수가 아니고 , 시간이 그 전보다 최소일 경우에만 값을 갱신한다.
         if (block>=0 && time<answer[0]){
             answer[0]=time;
             answer[1]=h;
         }
         
        }

        System.out.print(answer[0]+" "+answer[1]);

    }
}

 

[결과]

이렇게 푸니까 시간이 절반이나 줄었다. (약 400ms) 브루트포스 문제를 풀때 쓸때없는 반복문을 써서 풀진않았는지 좀 더 고민해보는 시간을 가져야 할 것 같다.