강의

https://www.youtube.com/watch?v=0DsyCXIN7Wg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=6

특징

LIFO 자료구조. 후입선출
STL 스택 - stack이 비었을 때 pop이나 top을 하면 런타임 에러.

구현

void push(int x) {
	dat[pos++] = x;
}

void pop() {
	--pos;
}

void top() {
	return data[pos - 1];
}

문제

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x05.md

1874

https://www.acmicpc.net/problem/1874

4
3
6
8
7
5
2
1
_
B

최종 B의 모습이 위와 같을 때
4가 오는 상황은 A 스택에 1,2,3,4를 넣은 다음 4를 pop해서 B스택에 넣은 경우. 이는 (+ + + +) (-) 로 표현됨

3
2
1	4
_	_
A	B

3은 이미 스택에 있기 때문에 그냥 pop을 해오면 됨. 이 때 스택의 top이 3이 아니라면 수열은 성립하지 않게 됨. 여기선 4를 pop하고 스택의 top이 3인 상태였음으로 수열이 성립. -

2	3
1	4
_	_
A	B

6이 오기 위해선 스택에 5,6을 넣은 다음 6을 pop해야함. (+ +) (-)

5	6
2	3
1	4
_	_
A	B

8이 오기 위해선 스택에 7,8을 넣은 다음 8을 pop 해야함. (+ +) (-)

7	8
5	6
2	3
1	4
_	_
A	B

이 다음부턴 그냥 pop을 쭉 하게 됨.

2493

https://www.acmicpc.net/problem/2493
와 스택 하나로 풀 수 있는 문제.
앞에 있는 빌딩부터 높이를 스택에 push시키며 진행함.
스택의 top이 현재 빌딩높이 보다 작으면 pop시켜버림. 지금 빌딩높이 보다 작다는 것은 다음에 진행할 빌딩 높이 비교에서 무시될 수 있다는 뜻.

6198

https://www.acmicpc.net/problem/6198
관점을 바꿔서 생각해야 함. 날 볼 수 있는 빌딩의 개수를 더한다고 생각하면 됨.
스택에 빌딩의 높이를 push해가면서 진행. 현재 위치에서 스택을 돌면서 내 높이보다 작거나 같은 원소는 pop시킴. 그리고 스택의 size만큼 더해가면서 답을 구함

17298

https://www.acmicpc.net/problem/17298
이건 입력 받아가면서 하면 순서가 안 맞음. 다 받아놓고 뒤에서부터 시작해야함

3015

https://www.acmicpc.net/problem/3015
와.. 진자 모르겠다 스택문제는 몰까..?
-> ㅇㅎ 일상적으로 생각하지 말고 그냥 텍스트 그대로 생각할 것. 마주본다니까 고개 들었다 내렸다 생각하게 되는데, 그냥 A와 B사이에 A보다도 작거나 같고 B보다도 작거나 같은 값들이 있는 쌍을 찾는다고 생각할 것

now를 받아가면서 스택에 push, pop을 하면서 진행.

스택은 오름차순으로 정렬된 상태가 될 것.

왜냐하면 top에 넣을 값보다 작은 값들은 pop시키면서 진행할 거기 때문에.

top에 넣을 값보다 작은 값들은 어차피 top에 가려져서 다음 원소들에 영향을 미치지 않게 됨. 그러니까 pop시키면서 ans에 값을 더해가면 됨.

이 때 now와 top이 같은 경우 문제 발생. 같은 값을 pop을 시켜야 더 작은 값들까지 pop시킬 수 있지만, 그렇게 되면 다음에 진행할 때 pop시켰던 값들만큼 더해줘야 하는데 그걸 알 수 없음.

그래서 스택을 pair로 만들어 stack<pair<int, int> > s; first에는 키(height)를 저장하고 second에는 같은 키가 연속된 횟수를 계속 더해줄 거임. 왜냐면 같은 값을 pop시켰던 횟수를 기억해야 하기 때문.

while (n--) {
		int now;
		cin >> now;
		int cnt = 1;
		while (!s.empty() && s.top().first <= now) {
			ans += s.top().second;
			if (s.top().first == now) cnt += s.top().second;
			s.pop();
		}
		ans += !s.empty();
		s.push(make_pair(now, cnt));
}

pop 반복문이 끝났다는 것은 now보다 더 큰 놈을 만났거나 스택이 비어있는 경우이게 됨.

이 때 스택이 비어있지 않은 경우 ans를 하나 증가시켜주면 됨. 왜 하나만 증가시켜 주면 되냐면, top은 now보다 크고 top 다음 값들은 now와 해당 값 사이에 top을 끼우고 있게 되는데, top이 이미 now보다 크기 때문에 마주볼 수 없는 놈들임

6549

https://www.acmicpc.net/problem/6549

나를 기준으로 큰 애들은 pop시켜야 한다는 것은 알았음. 왜냐하면 나 다음에 오는 애들은 나보다 더 큰 애들로 직사각형을 만들 수 없기 때문.

그래서 pop을 시킬 건데, 이 때 어떤 작업을 할지가 문제

스택은 오름차순 monotone 스택으로 관리 될 것임. pop을 시킬수록 점점 작은 숫자가 나올 것. 그럼 pop할 놈 * pop할 놈과 나와의 거리 => 넓이를 구해가며 max값을 찾아감

근데 답에선 왜 그냥 index를 저장하는 게 아닐까???

ㅇㅎ pop한 애들로도 내 높이로 직사각형을 만들 수 있기 때문에 pop을 멈추는 때의 index를 저장해야 함. 그렇기 때문에 나를 기준으로 크거나 같은 애들을 pop시키고 내 높이로 직사각형을 만들 수 있는 시작점을 업데이트 해나감

for (int i = 0; i < n; ++i) {
	int h;
	cin >> h;
	int idx = i;
	while (!s.empty() && s.top().X >= h) {
		ans = max(ans, 1LL * (i - s.top().Y) * s.top().X);
		idx = s.top().Y; // 이 부분!
		s.pop();
	}
	s.push(make_pair(h, idx));
}