HackerRank : Largest Rectangle

Largest Rectangle | HackerRank

문제 요약

• 건물의 갯수와 각 건물의 높이가 주어집니다.
• 일렬로 나열된 건물에서 안정적인 사각형 지대를 찾으려고 합니다.
  • 사각형의 값은 아래 공식으로 구합니다.
  •  k * min(h[i], h[i+1], ... , h[i+k-1])
  • 쉽게 말해 가장 큰 넓이를 가진 사각형이 안정적인 사각형 지대가 됩니다.

 

핵심 요약

 

위 문제는 stack, queue의 유형으로 분리되어있지만, 단순 Brute Force를 통해서도 접근이 가능합니다.

핵심을 요약하면 다음과 같습니다.

 

• A 건물의 높이가 3이라고 가정합시다.
• 이 건물의 왼쪽으로 loop를 돌렸을때, 높이가 3 이상인 건물이 있다면 그 건물은 A 건물이 만들어낼 사각형에 포함될 수 있습니다.
• 마찬가지로 오른쪽으로 loop를 돌렸을때, 높이가 3 이상인 건물이 있다면 그 건물은 A 건물이 만들어낼 사각형에 포함될 수 있습니다.

 

문제 풀이

 

class Result {
    public static long largestRectangle(List<Integer> h) {
        if(h.size()==1) return h.get(0);
        
        long ans = 0;

        for(int i=0; i<h.size(); i++){
            int width = 1;
            int height = h.get(i);
            for(int j=i+1; j<h.size(); j++){ // right
                if(h.get(j)>=height) width++;
                else break;
            }
            for(int j=i-1; j>=0; j--){ // left
                if(h.get(j)>=height) width++;
                else break;
            }
            ans = Math.max(ans,width * height);
        }
        
        return ans;
    }
}

위의 핵심 요약을 이해하면 코드를 이해하는데는 어려움이 없을겁니다.