[TIL-35/230928] 브루트포스, TDD와 리팩토링, 우아한 객체지향

[백준 18111 자바(Java)] 마인크래프트

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

18111번: 마인크래프트

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	1024 MB	54089	14225	10578	23.922%

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

입력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

 

첫 번째 풀이(오답)

문제 분석

1. 최대 높이와 최소 높이를 구하여 작업 시간을 각각 곱해 더 적은 작업 시간이 걸리는 방식으로 문제 해결 시도
2. 2중 반복문을 사용해 maxHeight, minHeight 구하기
3. 2중 반복문을 사용해 최댓값에 해당하는 블록의 개수와 최솟값에 해당하는 블록의 개수 구하기
4. 최대 높이 블럭의 개수 * 2와 최소 높이 블럭의 개수를 비교하고 최소 높이 블럭의 개수가 인벤토리에 있는 b보다 적으면 최소 높이 블럭의 개수만큼의 시간, 최대 높이만큼의 높이를 출력한다.

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 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 첫 번째 줄에서 n(행의 수), m(열의 수), b(가지고 있는 블록 수) 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        // 필드 정보를 저장할 2차원 배열 생성
        int[][] field = new int[n][m];
        
        // 필드의 최대 높이와 최소 높이 초기화
        int maxHeight = Integer.MIN_VALUE;
        int minHeight = Integer.MAX_VALUE;
        
        // 필드 정보 입력과 동시에 최대 높이와 최소 높이 갱신
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int value = Integer.parseInt(st.nextToken());
                field[i][j] = value;
                maxHeight = Math.max(maxHeight, value);
                minHeight = Math.min(minHeight, value);
            }
        }
        br.close(); // BufferedReader 닫기

        // 가장 높은 높이와 가장 낮은 높이의 블록 개수 계산
        int highCount = 0;
        int lowCount = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (field[i][j] == maxHeight) {
                    highCount++;
                }
                if (field[i][j] == minHeight) {
                    lowCount++;
                }
            }
        }

        int time = highCount * 2; // 최고 높이 블록을 모두 깎고 쌓는 데 걸리는 시간
        int height = minHeight; // 최소 높이에서 작업을 시작
        if (highCount * 2 > lowCount && lowCount <= b) {
            // 깎는 시간이 쌓는 시간보다 더 오래 걸리며, 가지고 있는 블록 수로 깎을 수 있는 경우
            time = lowCount; // 최소 높이 블록을 모두 깎고 쌓는 데 걸리는 시간
            height = maxHeight; // 최고 높이에서 작업을 시작
        }

        // 결과 출력
        System.out.println(time + " " + height);
    }
}

 

두 번째 풀이(정답)

문제 분석

1. 오답 풀이에서 높이를 최대, 최소만 생각하고 중간을 생각하지 않았다.
2. 반복문을 통해 최소 높이부터 최대 높이까지 증가시키며 높이를 정한다.
3. 정한 높이와 입력받은 높이의 차이를 저장한다.
4. 차이가 0보다 크면(블록을 쌓아야 하면) 차이 * 2만큼 시간을 추가하고 인벤토리에 diff만큼 늘린다.
5. 차이가 0보다 작으면(블록을 깍아야 하면) 차이만큼 시간을 추가하고 인벤토리에 diff만큼 뺀다.
6. 인벤토리가 0 이상이면서 시간이 최소시간인 경우 최소시간을 갱신하고 높이를 저장하여 출력한다.

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

public class Main {
    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));
        
        // 첫 줄에서 n(행의 수), m(열의 수), b(가지고 있는 블록 수) 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        // 지형 정보를 저장할 2차원 배열 생성
        int[][] field = new int[n][m];
        
        // 최대 높이와 최소 높이 초기화
        int maxHeight = Integer.MIN_VALUE;
        int minHeight = Integer.MAX_VALUE;
        
        // 지형 정보 입력과 동시에 최대 높이와 최소 높이 갱신
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int value = Integer.parseInt(st.nextToken());
                field[i][j] = value;
                maxHeight = Math.max(maxHeight, value);
                minHeight = Math.min(minHeight, value);
            }
        }
        br.close(); // BufferedReader 닫기

        // 최소 시간과 해당 높이를 저장할 변수 초기화
        int totalTime = Integer.MAX_VALUE;
        int height = -1;

        // 모든 높이에 대해 계산
        for (int i = minHeight; i <= maxHeight; i++) {
            int time = 0; // 현재 높이에서 걸리는 시간 초기화
            int inventory = b; // 현재 인벤토리 초기화

            // 전체 지형 순회
            for (int j = 0; j < field.length; j++) {
                for (int k = 0; k < field[j].length; k++) {
                    int diff = field[j][k] - i; // 현재 높이와의 차이 계산

                    // 차이가 양수인 경우 (블록을 쌓아야 하는 경우)
                    if (diff > 0) {
                        time += Math.abs(diff) * 2; // 쌓기 시간 추가
                        inventory += Math.abs(diff); // 인벤토리 조절
                    }

                    // 차이가 음수인 경우 (블록을 깍아야 하는 경우)
                    if (diff < 0) {
                        time += Math.abs(diff); // 깍기 시간 추가
                        inventory -= Math.abs(diff); // 인벤토리 조절
                    }
                }
            }

            // 인벤토리가 음수가 되지 않으면서 시간이 최소인 경우
            if (inventory >= 0 && time <= totalTime) {
                totalTime = time; // 최소 시간 갱신
                height = i; // 해당 높이 저장
            }
        }

        // 결과를 BufferedWriter를 통해 출력
        bw.write(totalTime + " " + height);
        bw.flush();
        bw.close();
    }
}

문제를 풀 때 항상 모든 경우의 수를 생각해야 한다.

이 문제가 바로 모든 경우의 수를 생각해야 하는 브루트 포스 알고리즘을 이용해서 풀 수 있는 문제다.

항상 예외가 발생하지 않도록 유념하면 문제를 풀자.

---

[우아한테크세미나] TDD와 리팩토링

https://prao.tistory.com/entry/%EC%9A%B0%EC%95%84%ED%95%9C%ED%85%8C%ED%81%AC%EC%84%B8%EB%AF%B8%EB%82%98-TDD-%EB%A6%AC%ED%8C%A9%ED%86%A0%EB%A7%81

[우아한테크세미나]TDD와 리팩토링

객체지향을 생각하면서 종종 학습했던 개념들을 자바지기 박재성님의 세미나를 들으면서 한번에 정리한 기분이었다.

개념에 대해서 설명하는 것으로 그치지 않고, 리팩토링 과정을 코드로 보여주셔서 이해하는 데 큰 도움이 되었다.

자세한 정리 내용은 위의 게시글을 참고 바란다.

 

오늘은 알고리즘과 TDD, 리팩토링에 대해서 공부했다.

아무래도 명절이다보니 마음이 붕 떠서 공부에 집중이 되지 않는다.

몇개월간 달려왔더니 번아웃이 조금 온 것 같다.

그로 인해 공부량이 조금 줄었는데, 내일부터는 다시 올바른 삶으로 돌아오려 노력하겠다.

화이팅하자.