문제 정보


문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
image image

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

//입력
4 4
3 0 1 4
//출력
5

풀이

단순 구현

가장 먼저 떠오른 풀이는 이중 배열을 생성하여 블록이 쌓여있는 공간을 1로 채워주고
for문으로 돌며 물이 채워지는 공간을 count하는 단순 구현이었다
하나의 열씩 볼 때, 두 블록 사이에 있는 공간은 모두 비가 고이는 것을 확인할 수 있었다
아래와 같이 하나의 열씩 확인하며 두 개의 블록 사이에는 비가 고이는 것으로 간주하여 물이 채워지는 공간을 확인하였다
image

bool변수를 하나 선언하고, 두 개의 블록 사이에 있을 경우 bool이 참이 되도록 한다
두 개의 블록 사이에 비가 고일 때 이 두개의 블록을 감싸고 있는 두 블록이라고 하겠다
다음과 같은 알고리즘을 통해 구현하였다

  • 열은 0 \~ H-1만큼, 행은 0 \~ W-2 (마지막에서 한 칸 앞의 원소)만큼 돌면서 해당 원소가 고여있는 빗물일 경우 count
  • 해당 원소가 블록이 아닐 경우) bool이 참일 경우에만 temp를 1씩 더한다
  • 해당 원소가 블록인 경우) 두 개의 조건을 체크한다
    • 해당 원소가 두 개의 블록중 뒷 블록일 경우 : temp를 count에 더해주고 temp를 초기화한다
    • 다음 원소가 블록이 아닐 경우(감싸고 있는 두 블록중 앞 블록일 경우) : bool <- true
    • 다음 원소가 블록일 경우(감싸고 있는 두 블록중 앞 블록일 경우) : bool <- false (블록이 연속할 경우)
  • array[i][j+1]를 검사할 경우 배열 범위를 초과하는 것을 막기 위해서 행을 W-2만큼만 돌았으므로 하나의 열이 끝날 때마다 그 열의 마지막 원소가 블록일 경우에만 temp를 더해주고 블록이 아닐 경우(앞 블록만 있고 뒤 블록은 없는 경우) temp를 초기화해준다
for i in 0...H-1{
    for j in 0...W-2 {
        //블록일 경우
        if array[i][j] == 1{
            //두 개의 블록 사이에 있는 물의 수 계산 후 뒤의 블록을 만난 경우
            if bool{
                count += temp
                temp = 0
            }
            //다음 원소가 블록이 아닐 경우 -> count 시작
            if array[i][j+1] == 0{
                bool = true
            //음 원소가 블록일 경우 -> count 하지 않는다 
            }else{
                bool = false
            }
        }
        //블록이 아닐 경우
        else{
            if bool{
                temp += 1
            }
        }
    }
    //한 행이 끝났을 때 마지막에서 -1인 원소가 1일 경우 count에 더해주고 0일 경우 temp 초기화              
    if array[i][array[i].endIndex-1] == 1{
        count += temp
    }
    temp = 0
    bool = false
}

max 사용

다음은 다른 사람들의 풀이를 보고 참고해서 푼 풀이이다
위처럼 단순 구현시 빠르게 코드를 짤 수 있지만 발상의 전환을 하면 짧은 코드로 문제를 해결할 수 있었다
각 행의 블록이 쌓인 높이를 의미하는 배열을 이용한다

  • 배열을 돌면서 해당 원소의 앞쪽 행들 중 최대 높이와 뒤쪽 행들 중 최대 높이를 구한다
  • 이 두 높이중 min값을 구한다
  • 이 mim값보다 해당 행의 높이가 낮으면 물이 고인다
  • 그때 result에 min값에서 해당 행의 높이를 뺀 값을 더한다
import Foundation
let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (H,W) = (n[0], n[1])
let arr: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
var result = 0
for j in 1...W-2{
    let m = min((arr[..<j]).max()!, (arr[j...]).max()!)
    if arr[j] < m {
        result += m - arr[j]
    }
}
print(result)

코드

전체코드 
import Foundation
let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (H,W) = (n[0], n[1])
var array: [[Int]] = Array(repeating: Array(repeating: 0, count: W), count: H)
let m = readLine()!.split(separator: " ").map{Int(String($0))!}
for i in 0...W-1{
    for j in stride(from: H-1, to: H-1-m[i], by: -1){
        array[j][i] = 1
    }
}
var bool = false
var count: Int = 0
var temp: Int = 0

for i in 0...H-1{
    for j in 0...W-2 {
        if array[i][j] == 1{
            if bool{
                count += temp
                temp = 0
            }
            if array[i][j+1] == 0{
                bool = true
            }else{
                bool = false
            }
        }
        else{
            if bool{
                temp += 1
            }
        }
    }
    if array[i][array[i].endIndex-1] == 1{
        count += temp
    }
    temp = 0
    bool = false
}
print(count)