[코딜리티] codility lesson 7 Stacks and Queues - StoneWall 100%

문제.

Programming language:                 C                        C++                        C#                        Go                        Java                        JavaScript                        Lua                        Objective-C                        Pascal                        PHP                        Perl                        Python                        Ruby                        Scala                        Swift 2                        Swift 3                        VB.NET                    

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 a zero-indexed 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:

int solution(int H[], int N);

that, given a zero-indexed 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.

Assume that:

• 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].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 2009–2017 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

풀이.

12345678910111213141516171819202122232425

// 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.*;
class Solution {
    public int solution(int[] H) {
        // write your code in Java SE 8
  if(H.length==0) return 0;
  if(H.length==1) return 1;
  int cuboid = 0;
  Stack<Integer> stack = new Stack<Integer>();
  for( int i : H){

   if(!stack.isEmpty()){
    while(stack.peek() > i){ stack.pop(); cuboid++; if(stack.isEmpty())break;}
    if(!stack.isEmpty() && stack.peek() == i) continue;
   }
   stack.push(i);
  }
  return stack.size() + cuboid;
    }
}

설명.

당신은 돌담을 지어야 합니다.
당신이 만들어야할 담의 설계도가 H배열에 들어 있습니다.
높이가 삐쭉뻬쭉 한 돌담을 만드는데 당신은 직육면체 의 돌을 쌓아서 만들어야 합니다.
돌담을 쌓을때 가장 적은 돌덩이를 사용하도록 할때 그 숫자를 구하시오.

돌담을 쌓는 규칙을 완성하는 것이 먼저일 것 같다.
그 규칙을 만들고 압축(?) 했더니 저런 코드가 나왔다.

if(H.length==0) return 0; //설계도가 비어 있다면 걍 끝내기
if(H.length==1) return 1; //담의 길이가 1이면 필요한 돌의 갯수는 한개

그 외에는 다음 동작을 수행한다.
"돌담 짓는데 필요한 돌 갯수 구하기 알고리즘 을 수행"
그 알고리즘을 설명 하자면...

ㅈㅇㅈ

이렇다.

설명하기가 어렵다야... 미안