StoneWall

https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

StoneWall coding task - Learn to Code - Codility

 

벽돌을 카운트하려면..

 

n번째 벽돌의 높이가 n-1번째 벽돌 높이와 달라야 한다.

 

벽돌의 높이가 높아질 때마다 벽돌의 높이를 stack에 쌓아주고,

마지막 벽돌 높이보다 낮은 벽돌이 오면 stack 에서 벽돌을 꺼내면서 벽돌끼리 높이를 비교한다.

 

만약 n번째 벽돌이

1) n-1번째 벽돌보다 높다면 n-1번째 위로 쌓여야 함

2) n-1번째 벽돌보다 낮다면 n-1 번째 벽돌을 꺼내고 카운팅

3) n-1번째 벽돌 높이와 같다면 이어진 벽돌

 

이게 Queue & Stack 카테고리에 있는 문제라는걸 인지하고 있어서 비교적 빠르게 풀었는데, 카테고리를 몰랐다면 시간이 오래 걸렸을 듯...

 

// 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) {
        // Implement your solution here

        Stack<Integer> walls = new Stack();

        int cnt = 0;
        for (int h : H) {

            int wall = 0;
            while (!walls.isEmpty()) {
                wall = walls.peek();
                if (wall > h) {
                    walls.pop();
                    cnt++;
                } else {
                    break;
                }
            }

            if (wall != h) walls.push(h);

        }

        return cnt + walls.size();

    }
}