[BOJ - JAVA] 14719 - 빗물(시뮬레이션, 구현)

# 주소

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

14719번: 빗물

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
    static int n, m;
    static int[][] arr;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        ArrayList<Integer> list;
        for(int i = 0; i < m; i++) {
            int temp = scan.nextInt();
            for(int j = n - 1; j >= n - temp; j--){
                arr[j][i] = 1;
            }
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            list = new ArrayList<>();
            for(int j = 0; j < m; j++) {
                if (arr[i][j] == 1) {
                    list.add(j);
                }
            }
            if(list.size() % 2 == 0 && list.size() > 0){
                for(int j = 0; j < list.size() - 1; j++){
                    int now = list.get(j);
                    int now2 = list.get(j + 1);
                    if(Math.abs(now - now2) > 1)
                        sum += now2 - now - 1;
                }
            }
            else if(list.size() % 2 == 1 && list.size() > 1){
                for(int j = 0; j < list.size() - 1; j++){
                    int now = list.get(j);
                    int now2 = list.get(j + 1);
                    if(Math.abs(now - now2) > 1)
                        sum += now2 - now - 1;
                }
            }
        }
        System.out.println(sum);
    }
}

사실 돌이켜보면 간단한 문제였습니다.

다른분들은 저보다 훨씬 쉽게 푸셨겠지만 전 한 30~40분 걸린 것 같네요.

또한 다른 분들은 저처럼 풀지 않고 이분탐색으로 푸셨던데 전 미처 생각하지 못했던 방법으로 푸시는걸 보고 많이 배웠습니다...

제가 푼 방법에 대해 소개해드리겠습니다.

제가 접근한 방식은 이러합니다.

1. arr를 2차원으로 구성하여 블럭이 있는 곳은 1, 없는 곳은 0으로 저장합니다.

2. 위의 행부터 탐색하여 총 n번의 행 값에 대해, 하나의 열에서 블럭이 있는 곳의 인덱스들을 ArrayList에 저장합니다.

3. list의 인덱스마다 sum에 더해줍니다.

이 방식이 시간이 많이 걸리는 것은 맞습니다..

아무래도 완전탐색방식이기도 하고 삼중for문으로 도니까요...

그래도 n값이 적어서 딱히 무리는 없다 판단했는데 바로 원큐에 정답은 뜨더라고요.

코드로 뜯어보며 살펴봅시다.

for(int i = 0; i < m; i++) {
    int temp = scan.nextInt();
    for(int j = n - 1; j >= n - temp; j--){
        arr[j][i] = 1;
    }
}

이 부분이 가장 어려울 수 있습니다.

temp는 입력값으로 주어지는 기둥의 높이인데요. 

2차원으로 선언한 arr[j][i]에 n-1부터 n - temp까지 밑!에서부터 1을 끌어올리며 삽입합니다.

따라서 만약 4 0 1 3 이렇게 입력된다면

1 0 0 0

1 0 0 1

1 0 0 1

1 0 1 1 이렇게 입력되겠지요.

 

이후 여기서부터 시선을 행 쪽으로 옮겨주세요. 

자

int sum = 0;
for(int i = 0; i < n; i++){
    list = new ArrayList<>();
    for(int j = 0; j < m; j++) {
        if (arr[i][j] == 1) {
            list.add(j);
        }
    }

list는 i가 올라갈 때마다 새로 선언하여 주시고 arr가 1이면 모두 list에 담습니다.

if(list.size() % 2 == 0 && list.size() > 0){
    for(int j = 0; j < list.size() - 1; j++){
        int now = list.get(j);
        int now2 = list.get(j + 1);
        if(Math.abs(now - now2) > 1)
            sum += now2 - now - 1;
    }
}
else if(list.size() % 2 == 1 && list.size() > 1){
    for(int j = 0; j < list.size() - 1; j++){
        int now = list.get(j);
        int now2 = list.get(j + 1);
        if(Math.abs(now - now2) > 1)
            sum += now2 - now - 1;
    }
}

그리고 list의 크기가 짝수이면서 0보다 클 때와 크기가 홀수이면서 1보다 클 때를 구분을 지었습니다.

(사실 구분짓고보니 이래나 저래나 하나로 통일해서 써도 되긴 합니다 ㅎ.)

각 경우에 대해, now - now2에 절댓값을 취하여 sum에 더해주되 1을 뺀채로 더해주겠습니다.

생각을 해보시면, 1과 3사이에 공간은 한 개인데 실제로 빼면 2개이죠??

그 말은 즉슨, 우리가 수학에서 1 < x < 3 이러한 부등식에서 정수가 되는 x는 오직 2입니다.

그런데 1 <= x < 3이 되게하는 x는 1, 2 등 존재할 수 있는데 이는 우리가 요구하는 계산법이 아닙니다.

오직 한 개가 나와야 하는데 말이지요.

마찬가지로 now2 에서 now를 빼게 되면 이는 1과 2에서 뺀다고 하였을 때 이는 사실상 붙어있는 블록인데도 불구하고 1이 추가적으로 생기기 때문에 반드시 1을 한 번 더 빼주셔야 하는 것입니다.

이 모든 과정을 list.size() - 1번만큼 진행해주시면 되겠습니다.

왜 list.size() - 1만큼 연산하냐구요???

-> list.get(j + 1)하게 되었을 때 list의 범위를 벗어나기 때문입니다.

예를 들어, [ 1, 2, 3, 4, 5]가 입력되어 있을 때 1과2, 2와3, 3과4, 4와5 총 4번 연산이 이루어져야 하는데 list.size() - 1을 안해주게 되면 5번 연산이 되어 인덱스의 범위를 벗어나게 되겠지요.

이 모든 과정을 마친 뒤 sum을 출력해주면 깔끔하게 시간초과 없이 출력됩니다.

감사합니다.