✅ stack

문제

링크

풀이

1. 문제 접근

오목하게 들어간 부분이 없어야 하므로 산 모양이 되어야 한다.
즉, 가장 긴 기둥을 기준으로 면적 계산을 다르게 해야한다.
1. 가장 긴 기둥 왼쪽 : 첫번째 기둥부터 가장 긴 기둥까지 탐색하면서 가장 최근에 나온 기둥보다 큰 기둥들만 기억해뒀다가 가장 긴 기둥이 나오면 이를 이용해 면적을 계산한다.
2. 가장 긴 기둥 오른쪽 : 마지막 기둥부터 가장 긴 기둥까지 탐색하면서 가장 최근에 나온 기둥보다 큰 기둥들만 기억해뒀다가 가장 긴 기둥이 나오면 이를 이용해 면적을 계산한다.

2. 자료구조 선택과 그 이유

가장 긴 기둥 왼쪽 : 가장 긴 기둥이 나올때까지 첫번째 기둥보다 큰 기둥을 기억해야 하므로 stack을 이용한다.
가장 긴 기둥 오른쪽 : 가장 긴 기둥이 나올때까지 마지막 기둥보다 큰 기둥을 기억해야 하므로 stack을 이용한다.

3. 문제 해결 로직 (풀이법)

1. 가장 긴 기둥을 찾는다.
2. 첫번째 기둥부터 가장 긴 기둥까지 탐색하면서 가장 최근에 나온 기둥보다 큰 기둥들만 기억해뒀다가 가장 긴 기둥이 나오면 이를 이용해 면적을 계산한다.
3. 마지막 기둥부터 가장 긴 기둥까지 탐색하면서 가장 최근에 나온 기둥보다 큰 기둥들만 기억해뒀다가 가장 긴 기둥이 나오면 이를 이용해 면적을 계산한다.

의사코드

cin >> N

for(i : 0~N){
	cin >> L >> H
	vector.push_back(pair<L, M>)
}

sort(vector.L) // 기둥의 위치를 순서대로 하기 위해 L을 기준으로 오름차순으로 정렬

idx = max(vector.second) // 가장 높은 기둥의 위치 저장

// 가장 긴 기둥 왼쪽
stack.push(vector[0])
for(i : 0 ~ idx-1){
	if(stack.top.H < vector[i].H){
    	stack.push(vector[i])
    }
}

tmp = vector[idx] // stack에서 나온 기둥 임시저장 (가장 긴 기둥 -> 첫기둥)
while(!stack.empty){ // stack에서 기둥을 하나씩 꺼내 면적 계산
	ans += (tmp.H - stack.top.H)*(tmp.L - stack.top.L)
    tmp = stack.top
    stack.pop
}

// 가장 긴 기둥 오른쪽
stack.push(vector[last])
for(i : last ~ idx-1){
	if(stack.top.H < vector[i].H){
    	stack.push(vector[i])
    }
}

tmp = vector[idx] // stack에서 나온 기둥 임시저장 (가장 긴 기둥 -> 첫기둥)
while(!stack.empty){ // stack에서 기둥을 하나씩 꺼내 면적 계산
	ans += (tmp.H - stack.top.H)*(tmp.L - stack.top.L)
    tmp = stack.top
    stack.pop
}

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

가장 긴 기둥을 기준으로 양쪽의 알고리즘을 다르게 구성하는 것이 핵심인거 같고
알고리즘 내에서 stack을 이용해 이전에 나온 기둥보다 큰 기둥을 저장해두는 것도 중요했던 문제