Baekjoon 14719 빗물 - 코딩테스트

 

14719번: 빗물

코딩테스트 대비 풀어본 문제이다.

처음 생각 - Stack

stack을 이용하여 풀려고 했다.

startBlock보다 큰 Block이 나올 때까지 stack에 넣어주었다.

for(int block = 1;block<W - 1;block++){
  if(startBlock > blocks[block]){
    stack.push(blocks[block]);
  } else {
    lowBlock = Math.min(startBlock, blocks[block]);
    startBlock = blocks[block];
    if(lowBlock != 0) {
      answer += GetRainWater(stack, lowBlock);
    }
  }
}

startBlock보다 큰 Block이 나온다면 startBlock-stack.pop()을 answer에 더해준다

static int GetRainWater(Stack<Integer> stack, int lowBlock) {
  int rain = 0;
  while(!stack.isEmpty()){
    rain += (lowBlock - stack.pop());
  }
  return rain;
}

반례 ⛔

testcase 6 1 4 0

각 index를 기준으로 maxLeft, maxRight 구하기 ❗

for (int block = 1; block < W - 1; block++) {
  int maxLeft = GetMaxLeft(blocks, block);
  int maxRight = GetMaxRight(blocks, block);
  if (Math.min(maxLeft, maxRight) < blocks[block])
    continue;
  answer += Math.min(maxLeft, maxRight) - blocks[block];
}
private static int GetMaxRight(int[] blocks, int index) {
  int max = -1;
  for (int i = index + 1; i < W; i++) {
    max = Math.max(max, blocks[i]);
  }
  return max;
}

private static int GetMaxLeft(int[] blocks, int index) {
  int max = -1;
  for (int i = 0; i < index; i++) {
    max = Math.max(max, blocks[i]);
  }
  return max;
}

왼쪽 오른쪽의 최대값을 찾은 후 더 작은 값과 뺀 것을 answer에 더해준다.

주의사항 ⛔

해당 index의 block이 maxLeft, maxRight보다 큰 경우는 넘어가야 한다.

전체 코드

for (int block = 1; block < W - 1; block++) {
  int maxLeft = GetMaxLeft(blocks, block);
  int maxRight = GetMaxRight(blocks, block);
  if (Math.min(maxLeft, maxRight) < blocks[block])
    continue;
  answer += Math.min(maxLeft, maxRight) - blocks[block];
}
private static int GetMaxRight(int[] blocks, int index) {
  int max = -1;
  for (int i = index + 1; i < W; i++) {
    max = Math.max(max, blocks[i]);
  }
  return max;
}

private static int GetMaxLeft(int[] blocks, int index) {
  int max = -1;
  for (int i = 0; i < index; i++) {
    max = Math.max(max, blocks[i]);
  }
  return max;
}