[백준] G3 8982 수족관 1 (java)

www.acmicpc.net/problem/8982

8982번: 수족관 1

 

풀이

 

1) N개의 수족관의 경계를 리스트에 담음. 담을때 수족관의 최대 너비(len)를 구해놓음

2) len 길이만큼의 1차원 배열 2개 생성. aquarium[], drainedWater[]

3) list를 탐색하면서 aquarium에 수족관의 깊이를 저장.

4) K 길이의 배열 생성. hole[]

5) hole에 입력값의 첫번째 숫자를 담음

6-1) hole의 갯수만큼 반복문을 돈다

6-2) h = hole[i] -> 구멍의 인덱스를 저장해 놓고

6-3) cur = aquarium[h] -> 현재의 높이를 저장해 놓고

6-4) drainedWater[h] = cur로 세팅 (해당 지점은 모든 물이 빠지므로)

6-5) h에서 왼쪽 오른쪽 탐색하면서 drainedWater 값을 갱신한다.

7) aquarium - drainedWater 출력

 

주의사항

 

1) 맨홀의 정보는 첫번째 숫자외엔 무쓸모이다.

2) 2차원 배열로 하면 시간초과다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_G3_8982_수족관1 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N, K, aquarium[], holeIndex[],drainedWater[];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		List<Node> list = new ArrayList<>();
		int len = 0;
		for(int n=0; n<N; n++) {
			tokens = new StringTokenizer(input.readLine());
			int c = Integer.parseInt(tokens.nextToken());
			int r = Integer.parseInt(tokens.nextToken());
			list.add(new Node(r, c));
			if(len < c) {
				len = c;
			}
		}
		aquarium = new int[len];
		drainedWater = new int[len];
		int cnt = 0;
		for(int i=1; i<list.size()-1; i=i+2) {
			int c1 = list.get(i).c;
			int c2 = list.get(i+1).c;
			for(int j = c1; j<c2; j++) {
				aquarium[cnt++] = list.get(i).r;
			}
		}
		K = Integer.parseInt(input.readLine());
		holeIndex = new int[K];
		for(int k=0; k<K; k++) {
			tokens = new StringTokenizer(input.readLine());
			holeIndex[k] = Integer.parseInt(tokens.nextToken());
		}// 입력 끝
		solve();
		int answer = 0;
		for(int i=0; i<aquarium.length; i++) {
			answer += aquarium[i] - drainedWater[i];
		}
		System.out.println(answer);
		
	}
	
	private static void solve() {
		for(int k=0; k<K; k++) {
			int h = holeIndex[k];
			int cur = aquarium[h];
			drainedWater[h] = cur;
			for(int i=h; i<aquarium.length; i++) { // 오른쪽
				if(cur < aquarium[i]) {
					drainedWater[i] = Math.max(drainedWater[i], cur);
				}else {
					cur = aquarium[i];
					drainedWater[i] = Math.max(drainedWater[i], cur);
				}
			}
			cur = aquarium[h];
			for(int i=h ; i>=0; i--) { // 왼
				if(cur < aquarium[i]) {
					drainedWater[i] = Math.max(drainedWater[i], cur);
				}else {
					cur = aquarium[i];
					drainedWater[i] = Math.max(drainedWater[i], cur);
				}
			}
		}
	}

	static class Node{
		int r;
		int c;
		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + "]";
		}
	}
	static String src =
			"8\r\n" + 
			"0 0 \r\n" + 
			"0 5\r\n" + 
			"1 5\r\n" + 
			"1 3\r\n" + 
			"2 3\r\n" + 
			"2 4\r\n" + 
			"3 4\r\n" + 
			"3 0\r\n" + 
			"1\r\n" + 
			" 0 5 1 5";
}

 

 

후기

 

하루종일 2차원배열로 풀면서 시간초과의 늪에 빠져서 허우적거리다가 결국 솔루션을 보았다.

진짜 매~~~우 어려운 문제였고 솔루션을 보지 못했으면 아마 1주일줘도 못풀었을것이다.

뭔가 시간초과가 날때 빠르게 해결하는 방법을 찾는것이 나에게 필요한 과제인것 같다.