6549_히스토그램에서 가장 큰 직사각형(반례 모음)

문제는 더보기!

 

히스토그램에서 가장 큰 직사각형 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

34137

8911

5736

25.762%

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

예제 입력 1 복사

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

예제 출력 1 복사

8
4000

 

 

 

처음에 이것저것 접근해보고 생각하다가 너무어려워서 고민이 많았던 문제이다.

 

고민하다가 인터넷에서 힌트를 조금얻고가자 생각해서 검색을 해봤더니 스택구조로 푸는 방법이 있어 읽고 구현을 해보았다.

 

이전에 동적계획법을 했던것처럼 히스토그램이 10개가 있다면 맨 처음것부터 하나씩 더해가면서 최대값을 갱신시키는 방식으로 하면 된다.

 

7 2 1 4 5 1 3 3

 

위와같은 예제가 들어오면 7,2,1,4,5,1,3,3 을 순서대로 넣어가면서 최대값을 갱신시키면 된다.

 

최대값을 얻기위해서 가장큰 키포인트는 숫자가 줄어드는 순간이다. 히스토그램이 점점 커지게 준다면, 박스의 넓이는 점점 커지게 될 것이다. 반대로 현재 히스토그램보다 작은 막대가 들어온다면 그 부분이 바로 값이 갱신될 수 있는 부분이다.

 

그래서 스택구조를 하나 만든 후에, 더 긴 히스토그램이 들어오면 push하고, 더짧은 히스토그램이 들어오면 들어온 히스토그램보다 작은 값을 만날때까지 스택에서 pop하면 된다.

 

이렇게 설명하면 어려울테니 진행과정에 따른 stack값을 한번 보자.

 

[[0, 0], [1, 2]]
[[0, 0], [2, 1]]
[[0, 0], [2, 1], [3, 4]]
[[0, 0], [2, 1], [3, 4], [4, 5]]
[[0, 0], [2, 1], [5, 1]]
[[0, 0], [2, 1], [5, 1], [6, 3]]
[[0, 0], [2, 1], [5, 1], [6, 3], [7, 3]]
[[0, 0], [8, 0]]

위와같은 순서로 스택구조가 변하게 된다. 참고로 stack에 들어가는 앞의값은 index,뒤에가 막대기의 높이값이다.

 

자, 그러면 더 작은 높이의 히스토그램이 들어오는

 

[[0, 0], [2, 1], [3, 4], [4, 5]]
[[0, 0], [2, 1], [5, 1]]

 

해당 부분을 봐보자.

 

4번째의 높이 5인 히스토그램 이후 5번째의 높이 1의 막대가 들어온 경우이다.

 

이경우

 

1 * 1 = 1 ( 새로 들어온 막대 )

5 * 1 = 5

4 * 2 = 8

1 * 3 = 3

 

위의 값중에서 가장 큰값을 고르면 된다. 그리고 그 값이 누적된 결과값보다 크다면 값을 갱신시키면 된다.

 

 

 

필자는 문제를 잘못읽어서 7 2 1 4 5 1 3 3 을 첫번째 막대의 높이가 7인경우로 생각했다...

7개의 막대기가 있는거고 2번째 리스트부터 본 값이니 헷갈리지 말자....

 

계속 통과가 안되서 반례만 엄청 찾아두었다! 필요한 사람들은 아래값을 복붙해서 넣으면서 테스트해보면 좋을 것 같다.

 

 

 

5 1 2 3 5 4
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
5 5 10 5 11 10
3 1000000000 1000000000 1000000000
5 1 2 3 4 5
7 0 5 7 5 5 3 1
4 1 4 3 3
5 1 3 2 4 6
4 2 3 2 1
3 3 4 3
4 1 3 3 1
4 0 1 2 3
1 5
6 7 0 3 1 0 3

 

아래는 정답들이다.

9
8
4000
25
3000000000
9
20
9
8
6
9
6
4
5
7