[백준][Java] 14719번 빗물 (시뮬레이션) #2

#2 

문제를 접근하는 방식 자체가 신박(내 기준)했고 진짜 깔끔했다

일단 문제에서 가로세로 width와 height를 준 이유가 있었음

일단 2차원 boolean배열 map을 선언 후에 map의 검은 부분을 true로 색칠해줌

 

그 다음에는 map의 column마다 세워진 block덩어리들이 오른쪽으로 레이져를 쏜다고 가정을 하면 됨

레이저를 쏠 때 바로 막히는 경우와

빈 공간이 존재해서 레이저가 나가다가 레이저가 다른 block덩어리에 막히는 경우가 빗물이 채워질 수 있는 경우인 것임

또 다른 경우는 빈 공간은 존재하지만 block덩어리에 막히지 못하는 경우임 이 경우는 빗물이 채워지지 않음

 

풀이법 자체는 굉장히 깔끔하고 명쾌해서 코드로만 옮기면 되는데

늘 그렇듯 2차원배열의 index는 조심해줘야함 이게 row인지 column인지 안 헷갈리게 하고

조건문에 <=를 할지 <를 할지 여하튼 arrayIndexOutOfException만 조심하면 된다

#1과는 정말 차원이 다른 깔끔한 풀이법이지만

실전에서는 생각하기 힘들 것 같다..ㅠㅠ

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        
        int height = stoi(str[0]);
        int width = stoi(str[1]);
        
        boolean[][] map = new boolean[height][width];
        str = br.readLine().split(" ");
        for (int j=0; j<str.length; j++) {
            int curr = stoi(str[j]);
            for(int i=0; i<curr; i++) {
                map[i][j] = true;
            }
        }
        
        /*for (int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                if(map[i][j])
                    System.out.print("1 ");
                else 
                    System.out.print("0 ");
            }
            System.out.println();
        }*/
        
        int res = 0;
        for (int j=0; j<str.length; j++) {
            int curr = stoi(str[j]);
            for(int i=0; i<curr; i++) {
                int temp = 0;
                for(int k=j+1; k<width; k++) {
                    if(!map[i][k])
                        temp++;
                    else {
                        res+=temp;
                        break;
                    }
                }
            }
        }
        
        System.out.println(res);
        
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}

 

 

 

 

 

 

#1

 

누더기로 짠 코드 (풀리긴 풀렸음.. #2로 풀고 나니까 현타오는 풀이방식)

풀이법은 

1. leftBlock을 기준으로 leftBlock보다 크거나 같은 rightBlock을 만날 경우 (이건 고인 빗물 구하기 쉬움)

2. leftBlock을 기준으로 leftBlock보다 크거나 같은 rightBlock이 존재하지 않는 경우

 

2가지 경우의 고인 빗물을 더해주면 된다

1번은 쉬운데

2번은 지금까지 쌓인 st의 원소들을 활용해서 구해줘야 하는데

1번의 케이스를 반대편에서 시작하면 된다.. 사실 코드가 너무 누더기라 성공하긴해도

따로 깔끔한 코드 보고 그걸로 갈아탈 것 같다..ㅠ

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        br.readLine();
        String[] str = br.readLine().split(" ");
        int[] blockArr = new int[str.length];
        for (int i = 0; i < str.length; i++) 
            blockArr[i] = stoi(str[i]);
            
        int res = 0;
        Stack<Integer> st = new Stack<>();
        int leftBlock = 0;
        
        for (int curr : blockArr) {
            if(curr>=leftBlock) {
                while(!st.isEmpty()) {
                    res += (leftBlock-st.pop());
                }
                leftBlock = curr;
            }
            else {
                st.push(curr);
            }
        }
        
        int rightBlock = 0;
        Stack<Integer> finSt = new Stack<>();
        while(!st.isEmpty()) {
            int curr = st.pop();
            if(curr>=rightBlock) {
                while(!finSt.isEmpty()) {
                    res += (rightBlock-finSt.pop());
                }
                rightBlock = curr;
            }
            else {
                finSt.push(curr);
            }
        }
        while(!finSt.isEmpty()) {
            res+=(rightBlock-finSt.pop());
        }
        
        
        System.out.println(res);
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}