[백준-자바] N_18111 마인크래프트

0woy·2024년 11월 28일

Java bruteforce 구현 백준

코딩테스트

목록 보기

42/42

📜 문제

각 칸의 높이를 저장한 NxM 배열, 현재 갖고 있는 블럭 수(b)가 주어짐
최단시간에 모든 칸의 높이가 같도록 해야함.
ⓛ 블럭 쌓기 = 1초
② 블럭 제거 & inventory 저장 = 2초
답이 여러 개인 경우, 높이가 가장 큰 값을 반환

생각하기

현재 배열 내에서 최소 높이(이하 min), 최대 높이(이하 max)를 알면,
답으로 나올 수 있는 높이의 범위는 min<= height <= max 임.
그러면 위 범위에서 반복문을 돌려서 가장 적은 시간 & 높이를 구하면 됨.

예제에 보면 같은 높이를 가진 칸이 여러 개일 수 있으니까, map을 이용해서 풀면 어떨까?
map: key: 높이, value: 해당 key 높이를 가진 칸의 개수

특정 높이 (height)를 기준으로,
count = map.get(h) : 배열 내 h 높이를 가진 칸의 개수

1. 높이(h) > height인 경우
높이 차이(diff) 만큼 블럭 제거
time += diff x count x 2 && b += count

2. 높이(h) < height인 경우
높이 차이 (diff) 만큼 블럭 쌓기
time += diff x count && b -= count

계산이 끝나고 난 후 현재 가지고 있는 블럭(b)가 음수인 경우,
사용할 수 있는 블럭을 초과했으므로 해당 높이는 답이 될 수 없음.

따라서 b >= 0인 경우만, 나올 수 있는 경우로 간주하고 진행해야한다.

🍳 전체 소스 코드

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

public class Main{
    static Map<Integer, Integer> ground;
    static int b;
    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());
        b = Integer.parseInt(st.nextToken());

        int cMax = -1;
        int cMin = 256;
        ground = new HashMap<>();
        while(n-- > 0){
            st= new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()){
                int k = Integer.parseInt(st.nextToken());
                ground.put(k,ground.getOrDefault(k, 0)+1);
                cMax = Math.max(cMax, k);
                cMin = Math.min(cMin, k);
            }
        }
        if(ground.keySet().size()==1){
            System.out.println(0+" "+cMax);
            return;
        }

        int res= Integer.MAX_VALUE;
        int height =0;
        for(int h =cMin;h<=cMax;h++){
            int time = getHeight(h);
            if(time > -1){
                if(time <= res){
                    res =time;
                    height = Math.max(height, h);
                }
            }
        }
        System.out.println(res+" "+height);
    }

    public static int getHeight(int height){
        int blocks = b;
        int  time =0;
        for(int h : ground.keySet()){
            int count =ground.get(h);
            int diff = Math.abs(height-h); // 높이차
            if(h>height){   // 제거
                time +=count*diff*2;
                blocks+=count*diff;
            }
            else if(h < height){    // 추가
                time +=count*diff;
                blocks-=count*diff;
            }
        }
        if(blocks<0){
            return -1;
        }
        return time;
    }
}

✍ 부분 코드 설명

변수 선언 & 초기화

public class Main{
    static Map<Integer, Integer> ground;
    static int b;
    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());
        b = Integer.parseInt(st.nextToken());

        int cMax = -1;
        int cMin = 256;
        ground = new HashMap<>();
        while(n-- > 0){
            st= new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()){
                int k = Integer.parseInt(st.nextToken());
                ground.put(k,ground.getOrDefault(k, 0)+1);
                cMax = Math.max(cMax, k);
                cMin = Math.min(cMin, k);
            }
        }
    ...

ground: 높이 별로 땅의 개수 저장
b: 현재 갖고 있는 블럭 개수
cMax: 배열 내 최대 높이
cMin: 배열 내 최소 높이

높이에 따른 땅의 개수를 groud에 저장하고, 최대 높이, 최소 높이를 구한다.

높이 계산하기

		...
        
  if(ground.keySet().size()==1){
            System.out.println(0+" "+cMax);
            return;
        }

        int res= Integer.MAX_VALUE;
        int height =0;
        for(int h =cMin;h<=cMax;h++){
            int time = getHeight(h);
            if(time > -1){
                if(time <= res){
                    res =time;
                    height = Math.max(height, h);
                }
            }
        }
        System.out.println(res+" "+height);
    }
        	...

- res : 최소 시간
- height: 최대 높이

key가 1개인 경우, 배열 내 모든 땅의 높이가 같다는 의미
-> 땅을 고를 필요가 없으므로 0, cMax 반환 및 종료

cMin ~ cMax 범위 내에서 각 값을 기준 높이(h)로, getHeight() 함수 호출

함수 반환 값이 -1이 아니면, 땅을 고를 수 있는 경우임
-> 현재 저장된 최소 시간(res) 보다 작거나 같은 경우, res값 갱신, 최대 높이(height) 갱신.

getHeight 함수

		...

   public static int getHeight(int height){
        int blocks = b;
        int  time =0;
        for(int h : ground.keySet()){
            int count =ground.get(h);
            int diff = Math.abs(height-h); // 높이차
            if(h>height){   // 제거
                time +=count*diff*2;
                blocks+=count*diff;
            }
            else if(h < height){    // 추가
                time +=count*diff;
                blocks-=count*diff;
            }
        }
        if(blocks<0){
            return -1;
        }
        return time;
    }
}