StoneWall (Codility) - Java

문제

N개의 원소가 담긴 배열 H가 주어진다. H[0] ~ H[N-1] 까지의 원소에는 벽의 높이 값이 들어간다. 이때 H 높이들을 만족하는 벽을 쌓기 위해서 최소 몇 개의 블럭이 필요한지를 구하는 문제이다.

 

해결 방법

스택을 활용하여 풀 수 있는 문제였다. 스택을 사용하는 이유는 서로 같은 높이에 있는 있거나 가장 낮은 높이의 값들은 블럭을 하나로만 써야 최소한의 블럭을 만들 수 있기 때문이다. 이러한 값들을 스택에 기록해 블럭을 어떻게 만들지 결정한다.

 

다음과 같은 규칙으로 높이 값을 순회돌며 스택을 사용한다.

(i번째 높이 값을 h라고 했을때)

1. 스택이 비어있다 => h를 push한다.

2. 스택 top의 값이 h보다 큰 경우 =>  pop 하고 배치 블럭 수를 1 증가시킨다.

3. 스택 top의 값이 h보다 작은 경우 => h를 push한다.

4. 스택 top의 값이 h와 같은 경우 => 아무런 처리 없이 다음 번째 높이값으로 continue한다. 

만약 3번 조건에 만족한다면 1, 2, 4번 조건에 만족할때까지 반복한다. 

 

이렇게 모든 높이 값을 순회한 후 (기록한 블럭 수) + (스택의 사이즈) 를 해주면 정답을 구할 수 있다.

 

그러면 이제 위 예제를 한번 풀어보자. 다음과 같이 높이 값이 주어져있다.

8  8  5  7  9  8  7  4  8

이제 이 높이 값을 순회돌며 알고리즘이 돌아간다면 다음과 같다. result를 배치하는 블럭 수라고 가정하겠다.

8 => 스택이 비어 있음 => 스택에 저장 [스택 : top(8)]

8 => top(8)과 같은 값이므로 생략

5 => top(8)보다 작으므로 pop한다. => result 1증가(1) => 스택에 저장 [스택 : top(5)]

7 => top(5)보다 크므로 => 스택에 저장 [스택 : top(7 5)]

9 => top(7)보다 크므로 => 스택에 저장 [스택 : top(9 7 5)]

8 => top(9)보다 작으므로 pop한다. => result 1증가(2) => top(7)보다 크므로 => 스택에 저장
[스택 : top(8 7 5)]

7 => top(8)보다 작으므로 pop한다. => result 1증가(3) => top(7)과 같으므로 생략
[스택 : top(7 5)]

4 => top(7)보다 작으므로 pop한다. => result 1증가(4) => top(5)보다 작으므로 pop한다. => result 1증가(5) => 스택이 비었으므로 => 스택에 저장 [스택 : top(4)]

8 => top(4)보다 크므로 => 스택에 저장 [스택 : top(4 8)]

최종적으로 result(5) + stack_size(2) = 7개가 벽을 만들기 위해 최소로 필요한 블럭 수가 된다.

 

구현 코드는 다음과 같다.

import java.util.Stack;
class Solution {
	public int solution(int[] H) {
		int result = 0;
		Stack<Integer> s = new Stack<Integer>();
		s.push(H[0]);
		for(int i = 1; i < H.length; ++i) {
			while(!s.empty()) {
				if(s.peek() > H[i]) {
					++result;
					s.pop();
				} else if(s.peek() < H[i]) {
					s.push(H[i]);
					break;
				} else break;
			}
			if(s.empty()) s.push(H[i]);
		}
		return result + s.size();
	}
}