[백준] 14719

코드 1, 실패, 230828

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


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        boolean dire = false;    // true는 증가
        int result = 0;
        String[] str = br.readLine().split(" ");

        String[] temp = br.readLine().split(" ");
        ArrayList<Integer> arr = new ArrayList<Integer>();
        ArrayList<Integer> point = new ArrayList<Integer>();

        for(int i = 0; i<temp.length; i++){
            arr.add(Integer.parseInt(temp[i]));
        }

        if(arr.get(0) > 0){
            dire = true;
        }

        for(int i = 0; i<arr.size()-1; i++){
            if((arr.get(i) > arr.get(i+1) && dire)){
                point.add(i);
                dire = false;
            } else if(arr.get(i) < arr.get(i+1)){
                dire = true;
            }
            if(i+1 == arr.size()-1 && arr.get(i+1) > 0){
                point.add(i+1);
            }
        }

        for(int i = 1; i<point.size()-1; i++){
            if(arr.get(point.get(i-1)) > arr.get(point.get(i)) && arr.get(point.get(i)) < arr.get(point.get(i+1))){

                point.remove(i);
                i -= 1;
            }
        }

        for(int i = 0; i<point.size()-1; i++){
            int a = point.get(i);
            int b = point.get(i+1);
            int num = arr.get(a) > arr.get(b)? arr.get(b) : arr.get(a);

            for(int j = a; j<b; j++){
                if(num - arr.get(j) > 0) {
                    result += num - arr.get(j);
                }
            }
        }
        System.out.println(result);
    }
}

설명

빗물은 증가 => 감소, 감소 => 증가 하는 블럭들을 기준으로 고인다고 생각
때문에 이 포인트들을 전부 찾고 인접한 포인트들 중에 더 작은 값을 기준으로 물이 고이는 것을 체크

• 424처럼 44로 포함되는 경우를 처리하지 못하는 문제 개선하고 인터넷의 대부분 반례 성공시켰지만 1%에서 계속해서 실패

코드 2, 성공, 230829

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


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int result = 0;
        String[] str = br.readLine().split(" ");

        String[] temp = br.readLine().split(" ");
        ArrayList<Integer> arr = new ArrayList<Integer>();

        for(int i = 0; i<temp.length; i++){
            arr.add(Integer.parseInt(temp[i]));
        }

        for(int i = 1; i<arr.size()-1; i++){
            int left = 0;
            int right = 0;
            for(int j = 0; j<i; j++){
                if(arr.get(j) > left){
                    left = arr.get(j);
                }
            }
            for(int j = i; j<arr.size(); j++){
                if(arr.get(j) > right) {
                    right = arr.get(j);
                }
            }
            int num = right > left? left : right;
            result += num - arr.get(i) > 0? num - arr.get(i) : 0;
        }
        System.out.println(result);
    }
}

설명

코드 1의 로직을 보다 간단하게 구현
for 1 ~ 뒤에서 두번째 인덱스

• 본인 기준 왼쪽에서 가장 큰 블럭, 오른쪽에서 가장 큰 블럭 구한 후 더 작은 값의 차이만큼 물이 고인다고 가정
  • 이 때 차이가 0보다 큰 경우만 취급

결국 모든 상황들을 코드로 핸들링하려하는 너무 사소한 생각부터 로직을 짜기 시작해 꽤 오래 걸린 것 같다. 보다 포괄적으로 해결할 수 있도록 짜보자