[BAEKJOON_14719 - JAVA] 빗물

문제

www.acmicpc.net/problem/14719

14719번: 빗물

 

 

풀이

• 처음에는 인덱스를 받음과 동시에 처리하려 시도했지만 실패
  -> 오른쪽에 물을 담을 빌딩의 위치를 특정하지 못했다.
• 이후 2차원 배열을 통한 구현
  -> 1차원 배열의 구현이 더 효율적일것으로 생각했다.
• 코드의 가독성을 위한 1차원 배열 구현
  변화 : 한번에 두개 사이의 물의 양을 계산 -> 각 위치의 빌딩에서의 물의 양을 계산
• 네이버,카카오 코딩테스트를 보면서 시간내에 정확하고 빠르게 푸는 연습이 필요하다고 느낌
  but 역시 오래걸렸다.(2시간) 알고리즘을 꾸준히!

 

 

과정

더 큰 건물들 사이에 끼어 있으면 빗물이 담긴다.

1. 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다.
2. 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다.
3. 그중 더 낮은 건물의 높이를 구한다.
4. 3번에서 구한 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다.
5. 위의 과정을 1번째, 마지막을 제외하고 현재 인덱스에서 담길 수 있는 빗물의 양을 합한다.

 

 

알고리즘 지식

• 구현

 

 

JAVA코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_14719_빗물 {

	static int[] map;
	static int ret, left, right;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		map = new int[W];
		ret = left = right = 0;

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < W; i++) {
			int N = Integer.parseInt(st.nextToken());
			map[i] = N;
		}

		// 인덱스마다 모이는 빗물 계산 ( 1번째 기둥과 마지막 기둥의 위치는 제외 )
		for (int i = 1; i < W - 1; i++) {
			left = right = 0;
			// 왼쪽에서 가장 높은 건물의 높이
			for (int j = 0; j < i; j++) {
				left = Math.max(map[j], left);
			}
			// 오른쪽에서 가장 높은 건물의 높이
			for (int j = i + 1; j < W; j++) {
				right = Math.max(map[j], right);
			}
            // 더 낮은 건물을 기준으로 현재 인덱스에 모이는 빗물
			if (map[i] < left && map[i] < right) {
				ret += Math.min(left, right) - map[i];
			}
		}
		System.out.println(ret);
	}
}