[알고리즘/Swift] 14719 빗물
문제 정보
문제
2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?
입력
첫 번째 줄에는 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하는 단순 구현이었다
하나의 열씩 볼 때, 두 블록 사이에 있는 공간은 모두 비가 고이는 것을 확인할 수 있었다
아래와 같이 하나의 열씩 확인하며 두 개의 블록 사이에는 비가 고이는 것으로 간주하여 물이 채워지는 공간을 확인하였다
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)