개발일지/Algorithm
백준 - 14719 빗물 [구현]
E-room
2023. 9. 22. 16:49
728x90
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
1. 문제 요약
블록들의 높이가 주어지고 블록들 사이에 고일 수 있는 빗물의 양을 구하는 문제입니다.
2. 파이썬
2 - 1. 접근 방법
백준 - 2304 창고 다각형 [구현]
2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내
e-room.tistory.com
이전에 풀었던 문제와 거의 유사하여 해당 방식을 다시 사용했습니다.
가장 높은 블록을 기준으로 세 부분으로 나누어 진행했습니다.
2 - 2. 코드
def solution(w: int, blocks: list):
answer = 0
highest = max(blocks)
# 정방향
now_highest = 0
stop_index1 = 0
for i in range(w):
if blocks[i] >= highest:
stop_index1 = i
break
elif blocks[i] < now_highest:
answer += now_highest - blocks[i]
else: # blocks[i] > now_highest:
now_highest = blocks[i]
# 역방향
now_highest = 0
stop_index2 = 0
for i in range(w - 1, -1, -1):
if blocks[i] >= highest:
stop_index2 = i
break
elif blocks[i] < now_highest:
answer += now_highest - blocks[i]
else:
now_highest = blocks[i]
# 중간 부분 계산
for i in range(stop_index1 + 1, stop_index2):
answer += highest - blocks[i]
print(answer)
h, w = map(int, input().split())
blocks = list(map(int, input().split()))
solution(w, blocks)
3. 자바
3 - 1. 접근 방법
현재 위치에 물이 고일 수 있는 양에 집중하는 방법
즉, 현재 인덱스의 양 옆으로 자신보다 높은 블록이 존재하는지 체크하여 고일 수 있는 양을 계산한다.
3 - 2. 코드
// 메인 로직
static int solution(int[] blocks) {
int answer = 0;
for (int i = 1; i < blocks.length - 1; i++) {
int leftHighest = getMax(blocks, 0, i);
int rightHighest = getMax(blocks, i + 1, blocks.length);
int compare = Math.min(leftHighest, rightHighest);
if (compare > blocks[i]) {
answer += compare - blocks[i];
}
}
return answer;
}
// 편의 메서드 다양한 방식으로 대체가능
private static int getMax(int[] arr, int start, int end) {
int max = Integer.MIN_VALUE;
for (int i = start; i < end; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
3 - 3. 전체 코드
728x90