[codility] StoneWall

StoneWall

Cover "Manhattan skyline" using the minimum number of rectangles.

Task Score

100%

Correctness

100%

Performance

100%

---

 

아니.. painless라고 했잖아요 ㅠ

짱구 굴리느라 너무 힘들었다.

스택도 써보고 큐도 써보고 리스트도 써보고 콜렉션도 써보고 해쉬셋도 써보고 난리난리를 치다가

혼자 그림그리고 순서도 써보고 글로 적어보고 난리난리를 치다가

결국 누구누구한테 수학적으로 힌트를 받기는 했지만 결국 성공했다....

자존심상해..☆

 

아무튼~~ 설명을 해보자면,

 

힌트는 받았지만 코드를 받은게 아니라 그냥 수학적 접근법 정도였어서

얘기를 듣고나니 가닥은 잡혔지만 정확히 로직을 어떻게 짜나갈지 고민이됐다.

그래서 열심히 그림판으로 그림을 그려봤는데, 막상 해보니 스택으로 하기 딱 좋았다.

그림으로 로직을 정리하고, 바로 코드 작성에 들어갔다.

코드 짜보니 왜 painless인지 알겠네..(코쓱)

 

x
// 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");
​
class Solution {
    public int solution(int[] H) {
        int answer = 0;
        Stack<Integer> s = new Stack<>();
        
        for (int i = 0; i < H.length; i++) {
            
            if (s.empty() || H[i] > s.peek()) {
                answer++;
                s.add(H[i]);
            } else if (H[i] < s.peek()) {
                s.pop();
                i--;
            }
        }
        
        return answer;
    }
}

 

코드 설명하는 것보다 내가 그렸던 그림으로 설명해주는게 나을것 같아 아래에 그림도 첨부한다.

(그렸던것 undo 후 redo 하는거라 위에 노티가 뜨긴 하지만..ㅎㅎ...내용은..보이니까.)