7-4. StoneWall
You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by an array H of N positive integers. H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall's left end and H[N−1] is the height of the wall's right end.
The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular). Your task is to compute the minimum number of blocks needed to build the wall.
Write a function:
class Solution { public int solution(int[] H); }
that, given an array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.
For example, given array H containing N = 9 integers:
H[0] = 8 H[1] = 8 H[2] = 5
H[3] = 7 H[4] = 9 H[5] = 8
H[6] = 7 H[7] = 4 H[8] = 8
the function should return 7. The figure shows one possible arrangement of seven blocks.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array H is an integer within the range [1..1,000,000,000].
당신은 돌벽을 쌓으려고 합니다. 벽은 직선으로 N 미터 길이여야 하고, 두께는 일정해야 하지만, 높이는 장소마다 다르게 해야 합니다. 벽의 높이는 N개의 양의 정수로 이루어진 배열 H로 지정됩니다. H[I]는 벽의 왼쪽 끝에서 오른쪽으로 I에서 I+1 미터까지의 높이입니다. 특히, H[0]은 벽의 왼쪽 끝의 높이이고, H[N−1]은 벽의 오른쪽 끝의 높이입니다.
벽은 직육면체 돌 블록으로 만들어져야 합니다 (즉, 이러한 블록의 모든 면은 직사각형입니다). 당신의 과제는 벽을 쌓는 데 필요한 최소 블록 수를 계산하는 것입니다.
다음과 같은 함수를 작성하세요:
class Solution {
public int solution(int[] H);
}배열 H가 N개의 양의 정수를 포함하고 있을 때, 벽의 높이를 지정하는 배열 H가 주어지면, 벽을 쌓는 데 필요한 최소 블록 수를 반환하는 함수를 작성하세요.
예를 들어, N = 9인 배열 H가 주어졌을 때:
H[0] = 8 H[1] = 8 H[2] = 5
H[3] = 7 H[4] = 9 H[5] = 8
H[6] = 7 H[7] = 4 H[8] = 8함수는 7을 반환해야 합니다. 그림은 7개의 블록으로 가능한 배치를 보여줍니다.
다음 가정을 위한 효율적인 알고리즘을 작성하세요:
N은 [1…100,000] 범위 내의 정수입니다.
배열 H의 각 요소는 [1…1,000,000,000] 범위 내의 정수입니다.
문제풀이
import java.util.Stack;
class Solution {
public int solution(int[] H) {
Stack<Integer> stack = new Stack<>();
int blockCount = 0;
for (int height : H) {
while (!stack.isEmpty() && stack.peek() > height) {
stack.pop();
}
if (stack.isEmpty() || stack.peek() < height) {
stack.push(height);
blockCount++;
}
}
return blockCount;
}
}위 문제는 계속 제출 시에 계속 오답처리가되어 해설을 참고했습니다 ㅠㅠ
문제의 지문이 이해가 잘 안되는 부분들이 있는데
해당 문제는 블록이 바로 이전 블록과 동일하면 블록 변경이 없고
높이가 변하면 블록을 다른 블록으로 변경하고 블록 수를 추가하면 됩니다.
예를 들어, 주어진 배열 H = [8, 8, 5, 7, 9, 8, 7, 4, 8]의 경우
처음에 높이 8로 시작합니다. 첫 번째 블록을 추가합니다.
두 번째 위치에서도 높이 8이므로 같은 블록을 유지합니다.
세 번째 위치에서 높이가 5로 감소합니다. 새로운 블록을 추가합니다.
네 번째 위치에서 높이가 7로 증가합니다. 새로운 블록을 추가합니다.
다섯 번째 위치에서 높이가 9로 증가합니다. 새로운 블록을 추가합니다.
여섯 번째 위치에서 높이가 8로 감소합니다. 새로운 블록을 추가합니다.
일곱 번째 위치에서 높이가 7로 감소합니다. 새로운 블록을 추가합니다.
여덟 번째 위치에서 높이가 4로 감소합니다. 새로운 블록을 추가합니다.
아홉 번째 위치에서 높이가 8로 증가합니다. 새로운 블록을 추가합니다.
이렇게 하면 총 7개의 블록이 필요합니다.
여기서 첫번째 블록은 항상 필요하므로 별도로 세지않고 기본 블록으로 간주하여
새로 추가되는 블록의 갯수만을 카운팅해야 합니다.
제출결과
문제풀어보기 -> https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/
