바킹독 0x05 문제8 / 백준 6549번 히스토그램에서 가장 큰 직사각형

 

후딱 풀자더니..

일주일이 넘게 지났다.

요즘 지친 거 같다. 뭔가 의욕이 없다.

그래서 자꾸 멍하게 되고 풀어지는 거 같다.

어제는 나름..?! 힐링여행 대전을 다녀왔다.

케이크집이 유독 좋았다.

오늘 점심에 사온 빵과 케이크를 먹었는데

참 맛있었다.

왕복 7시간 걸렸는데....흠.. 다음에도 갈 수 있을지나 모르겠다.

---

 

늘 생각하는거지만 문제 자체도 이해하는 게 힘들다.

 

가장 넓은것을 찾는 것이기 때문에 

위에 그림과 같이 지금은 가장 큰 게 색칠되어 있지만

21 도 이론상 1*2인 직사각형이 생기긴 한다.

이런 걸 고려했을 때....

일단 앞숫자와 뒷숫자를 비교하고 더 작은 크기랑 세었던 횟수를 곱해주면 되지 않을까?라는 생각을 했다.

나도 쓰면서 무슨 뜻으로 말하는지 헷갈리긴 한다.

 

일단, 스택은 두 개 필요하다.

높이 그다음에 가로, 즉 왼쪽으로 몇 번 갔는지 인덱스를 셀 것이다.

 

먼저 스택에 들어있던 막대보다 새로 들어온 막대기가 더 작으면,

작은 방향으로 계산해야 하니까 더 이상 먼저 들어왔던 길이가 긴 애는 필요가 없다.

그래서 pop 해줘야 하고,

pop 해주기 전에 면적을 계산해줘야 한다.

이 면적을 계산해 주는 게 나는 힘들었다.

가로길이를 어떻게 계산해야 할지 감이 안 왔다.

 

그래서 지피티의 도움을 받았다.

그것을 인덱스로 정해놓고 시작하자고 했다.

막대기가 3개 들어왔다면

0 1 2 일거고

그 폭을 구하려면

오른쪽에서 왼쪽을 빼고 +1을 해준다.

 

L=0, R=0 → 폭=1

L=0, R=1 → 폭=2

L=1, R=3 → 폭=3 (3-1+1=3)

 

 

이런 계산을 베이스로 시작하게 된다.

 

 

자, 우리는 push 하면서 

높이인 h와 가로인 idx를 넣게 된다.

그 인덱스부터 시작할 테니 시작점 즉 L은 정해진 것이다.

 

이제 R 차례다.

이 R의 끝? 을 생각했을 때,

우리가 위에 말한 새로운 막대기가 원래 있던 막대기 보다 작을 때 이다.

 

즉 5 뒤에 3이 들어오게 되면

직사각형을 만들기 위해 기준점이 되던 5가 더 이상 5의 높이로 직사각형을 만들 수 없기 때문에

이제 기준점을 3으로 바꿔야 하는 것이다.

 

3으로 바꾸기 전에 우리가 해야 할 일은

1. 5가 기준이었을 때 있던 직사각형의 넓이를 구하고

2. 더 이상 필요 없으니 pop 해줘야 한다.

 

1. 5가 기준이었을 때 있던 직사각형의 넓이를 구하고

이 경우 지금.. 3이 기준점이 되기 직전이었으니까

i -1 이 5 일거고

왼쪽은 idx이고 오른쪽은 i -1 이 되게 된다...

 

그럼 폭 구하는 식은..

(i - 1) - idx + 1

즉.. i - idx가 되게 된다. ㅋㅋㅋㅋㅋ

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아 너무 어려워!!!!!!!!!!!!!
악!!!!!!!!!!!!

 

이제 문제를 풀어보자

 

아! 중요한 것은 

가로 곱하기 세로인데

세로만 해도 높이가 10의 9승이라..

int로는 택도 없다.

 그래서! long long으로 해줘야 한다.

 

 

여기서 어려웠던 건 아까 직사각형 만드는 폭 공식..? 이였다.

 

밑에서도 n - S.top(). second 인 이유는

이제 마지막 검토는

스택에 있는 길이만큼의 직사각형 이기 때문에

맨 오른쪽은 n이니까 거기서 빼주면 크기가 되게 된다.

정확히 말하면 여기서는 n까지 루프를 도니까

제일 끝은 n - 1 이 되고

폭 공식에 의해 n - 1 + S.top().second +1

R - L + 1

그렇다.

---

너무 어려워서 머리가 아프다....

 

사실 지금까지 풀던 스택의 패턴은

넣어보고, 전에 친구( top )랑 비교해서 크면 top 빼주고

안 크면 다른 거 비교하는 패턴이었다.

 

그런 패턴이었음에도 참 어려웠다.

어려웠다.

 

다 풀긴 했는데.....

너무 어려워서 아무 생각이 없다.

 

ㅎㅋ 그다음 거도 잘할 수 있겠지!?

파이팅이다!