Codility Java StoneWall

문제

Link

코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

import java.util.Stack;

class Solution {
  public int solution(int[] H) {
    int result = 0;
    Stack<Integer> stack = new Stack<>();
    for (int height : H) {
      while (!stack.isEmpty() && stack.peek() > height) {
        stack.pop(); // Remove higher than new stone wall.
      }
      if (stack.isEmpty() || stack.peek() < height) {
        stack.push(height); // Add new stone wall.
        result++;
      }
    }
    return result;
  }
}

설명

1. 돌담의 높이를 임시 저장하기 위한 저장소로 Stack을 사용한다.
2. 주어진 배열 H를 반복하여 블록의 수를 계산한다.
   • 돌담의 높이를 임시 저장한 stack이 비어있지 않을 떄, stack에서 꺼낸 돌담의 높이가 주어진 돌담의 높이보다 큰 값들을 제거한다.
   • 주어진 돌담의 높이가 stack에서 꺼낸 돌담의 높이보다 높은 경우는 기존 블록에 새로운 블록을 추가하여 사용하므로 패스한다.
   • 주어진 돌담의 높이가 stack에서 꺼낸 돌담의 높이와 같은 경우는 같은 블록을 사용하므로 무시한다.
   • 주어진 돌담의 높이가 stack에서 꺼낸 돌담의 높이보다 낮은 경우는 새로운 블록을 사용해야 하므로 기존 값을 지운다. - stack이 비어있거나 stack에서 꺼낸 돌담의 높이가 주어진 돌담의 높이보다 작으면 새로운 블록을 추가해야 하므로 stack에 추가하고, 블록의 수를 저장하는 result를 증가시킨다.
3. 반복이 완료되면 블록의 수를 저장하는 result를 주어진 문제의 결과로 반환한다.

결과

Link

소스

Sample Code는 여기에서 확인 가능합니다.