[JAVA-자바] 3015번: 오아시스 재결합

소스코드:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    long result = 0;
    int N = Integer.parseInt(br.readLine());
    int[] arr = new int[N];
    for (int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(br.readLine());
    }

    // key - sameCount
    Stack<int[]> stack = new Stack<>();
    for (int i = 0; i < N; i++) {
      int height = arr[i];
      int sameCount = 1;

      // 스택 맨위가 나보다 작으면, 나는 다 볼 수 있음
      while (!stack.isEmpty() && stack.peek()[0] < height) {
        result += stack.pop()[1];
      }

      // 스택 맨위가 나랑 같으면(같은 키끼리 병합)
      if (!stack.isEmpty() && stack.peek()[0] == height) {
        sameCount = stack.peek()[1] + 1;
        result += stack.pop()[1];

        // 내가 제일 큰게 아니면, 나보다 큰애가 하나는 있음
        if (!stack.isEmpty()) {
          result++;
        }
      } else {
        // 스택 맨위가 나보다 크면, 나는 그 애를 볼 수 있음
        if (!stack.isEmpty()) {
          result++;
        }

      }
      stack.push(new int[]{height, sameCount});
    }

    bw.write(String.valueOf(result));
    bw.close();
    br.close();
  }
}

 

글의 내용 중 잘못된 점이나 수정이 필요한 부분, 혹은 궁금한 사항이 있다면 언제든 댓글로 남겨주시면 감사하겠습니다.

여러분의 피드백은 더 나은 글을 작성하는 데 큰 도움이 됩니다. 감사합니다.