[14719번][Java] 빗물

www.acmicpc.net/problem/14719

14719번: 빗물

 

해결 방법

 

물을 가두는데 leftWall, rightWall가 필요하다고 합시다.

leftWall에 임의의 높이가 정해졌다고 할때, rightWall의 높이가 이보다 크거나 같을 경우에만 그 사이 담긴 물의 양을 계산합니다.

그리고 이걸 정방향, 역방향으로 둘다 해줍니다.

 

 

 

...

public class Main {
    static int H,N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        List<Integer> blocks = new ArrayList<>();
        while(st.hasMoreTokens()) {
            blocks.add(Integer.parseInt(st.nextToken()));
        }

        //정방향
        Wall baseWall = new Wall(0, blocks.get(0));
        int amount = 0;
        for (int i = 1; i < blocks.size(); i++) {
            Wall currentWall = new Wall(i, blocks.get(i));
            if(baseWall.height <= currentWall.height) {
                amount += calcRainAmount(baseWall, currentWall, blocks);
                baseWall = currentWall;
            }
        }
//        System.out.println(amount);
//        System.out.println(baseWall.index);
        //역방향
        int tallestWallIndex = baseWall.index;
        int lastIndex = blocks.size()-1;
        baseWall = new Wall(lastIndex, blocks.get(lastIndex));
        for (int i = 1; i < blocks.size()-tallestWallIndex; i++) {
            Wall currentWall = new Wall(lastIndex-i, blocks.get(lastIndex-i));
            if(baseWall.height <= currentWall.height) {
                amount += calcRainAmount(currentWall, baseWall, blocks);
                baseWall = currentWall;
            }
        }
        System.out.println(amount);

    }

    private static int calcRainAmount(Wall leftWall, Wall rightWall, List<Integer> blocks) {
        int amount = 0;
        for (int i = leftWall.index+1; i < rightWall.index; i++) {
            amount += Math.min(leftWall.height, rightWall.height) - blocks.get(i);
        }
        return amount;
    }
}
class Wall {
    int index, height;

    public Wall(int index, int height) {
        this.index = index;
        this.height = height;
    }

    @Override
    public String toString() {
        return "Wall{" +
                "index=" + index +
                ", height=" + height +
                '}';
    }
}