백준 [자바 java] 14719 : 빗물

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

14719번: 빗물

 

풀 문제 찾다가 우리학교 문제 발견해서 풀어봤어요.

처음 양 옆에가 벽인 것만 물을 채웠는데 그럼 절대 안되더라구요.

그래서 for문을 이용해서 가로로 한 줄씩 왼쪽부터 탐색하면서 벽이 나오면 다음 벽이 나올 때까지 세고.. 뭐 이런 알고리즘을 생각했는데 너무너무 복잡했어요.

생각해보니까 아래부터 가로로 한 줄씩 벽 사이의 간격을 재면 되더라구요!
그래서 stack을 이용해서 벽이 있는 곳의 위치를 넣고 차례로 빼서 간격을 세어주었답니다.

근데 제 코드에 한가지 문제점이 있는데, 제가 수를 입력받고 배열을 벽으로 채우는 과정에서 뭔가 잘못했는지 웅덩이가 뒤집어진(?) 형태가 되어버렸어요. 근데 문제푸는데 지장은 없어서(어차피 한 줄씩 보니까) 그냥 풀었습니다!

 

 

 

풀이코드

 

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


public class Main {



    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());

        int arr[][] = new int[n][m];

        st = new StringTokenizer(br.readLine());

        for(int i = 0;i<m;i++){
            int k = Integer.parseInt(st.nextToken());

            for(int j = k-1 ;j>=0;j--){
                arr[j][i] = 1;
            }
        }

        

        int ans = 0;

        Stack<Integer> s = new Stack<>();

        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(arr[i][j] == 1){
                    s.push(j);
                }
            }

            if(s.isEmpty()) continue;
            int front = s.pop();

            while(s.isEmpty()!= true){
                int k = s.pop();
                ans += Math.abs(k-front)-1;
                front = k;
            }
        }

        System.out.println(ans);




    }
}