[백준] 히스토그램

[hye-on]

🔗 히스토그램

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

// 양방향으로 검사
// 스택은 오름차순으로 쌓기

// 들어오는 애보다 스택의 top이 더 크면 pop
// 같으면 arr 값 += 

int n;
stack<pair<int, int>>s;
int main() {
	cin >> n;

	vector<int>histogram(n);
	

	for (int i = 0; i < n; i++) {
		cin >> histogram[i];
	
	}

	
	vector<int>arrLeft(n);
	stack<pair<int, int>>st; // 높이,idx
	for (int i = 0; i < n; i++) {
		while (!st.empty() && st.top().first >= histogram[i]) {
			arrLeft[i]++;
			arrLeft[i] += arrLeft[st.top().second];
			st.pop();
			
		}
		

		st.push({ histogram[i],i });
	}

	vector<int>arrRight(n);
	st = s;
	for (int i = n-1; i >= 0; i--) {

		while (!st.empty() && st.top().first >= histogram[i]) {
			arrRight[i]++;
			arrRight[i] += arrRight[st.top().second];
			st.pop();
		}

		st.push({ histogram[i],i });
	}


	/*for (int i = 0; i < n; i++) {
		cout << arrLeft[i] << " " << arrRight[i] << endl;

	}*/

	int ans = 0, area = 0;
	for (int i = 0; i < n; i++) {
		if (histogram[i] == 0)
			continue;
		area = histogram[i] * (arrLeft[i] + arrRight[i] + 1);
		ans = max(area, ans);
	}
	cout << ans;
}

코드 풀이2

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

// 스택의 top이 높이가 됨 

int n;
stack<pair<int, int>>s;
int main() {



	cin >> n;

	vector<int>histogram(n+1);
	

	for (int i = 0; i < n; i++) {
		cin >> histogram[i];
	
	}

	histogram[n] = - 1; //강제로 모든 스택을 비우면서 검사함
		
	stack<pair<int, int>>st; // 높이,idx
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		int minPos = i;
		while (!st.empty() && st.top().first >= histogram[i]) {
			auto [h, pos] = st.top();
			ans = max(h * (i - pos), ans);
			minPos = min(i, st.top().second); // 2, 1일때 2를 pop함 하지만 1의 높이로 0번째 인덱스까지 그릴 수 있음
			st.pop();
		}

		st.push({ histogram[i],minPos });
	}



	cout << ans;
}

코드 풀이 3

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

//분할 정복
//왼쪽, 오른쪽, 걸치기
// O(N log N)

int n;
vector<int>histogram(100000);

int recursion(int start, int end) {
	if (start == end)
		return histogram[start];

	int mid = (start + end) / 2;
	int left = mid, right = mid + 1;
	int high = min(histogram[mid], histogram[mid + 1]);
	int maxN = 2 * high;
	while (start<left || right < end) {

	
		// 오른쪽이 더 크거나 왼쪽이 더 갈 곳이 없을 때
		if (right < end && (start == left || histogram[left - 1] < histogram[right + 1])) {
			right++;
			high = min(high, histogram[right]);
		}
		else {
			left--;
			high = min(high, histogram[left]);
		}
		maxN = max(maxN, high * (right - left + 1));
	}

	return max({ maxN, recursion(start,mid),recursion(mid + 1,end) });
}
int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> histogram[i];
	}

	cout << recursion(0, n - 1);

}

코드 풀이4

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

//세그먼트 트리

int n;
vector<int>histogram(100000);
vector<int>tree;

int init(int start, int end, int node) { // target의 start, end
	if (start == end)
		return tree[node] = start; //리턴 꼭해야함

	int mid = (start + end) / 2;
	
	int leftIdx = init(start, mid, node * 2);
	int rightIdx = init(mid + 1, end, node * 2 + 1);

	if (histogram[leftIdx] <= histogram[rightIdx])
		return tree[node] = leftIdx; //세그먼트 트리에 넣어주고 리턴
	else
		return tree[node] = rightIdx;

}



//구간의 제일 작은 높이 구하기
// 타겟 범위 (변하지 않음), 트리 인덱스, 트리 범위
int findHeightIdx(int start, int end, int node, int treeLeft, int treeRight) {
	if (start <= treeLeft && treeRight <= end)
		return tree[node];

	if (end < treeLeft || treeRight < start)
		return -1;

	int mid = (treeLeft + treeRight) / 2;
	int leftIdx = findHeightIdx(start, end, node * 2 , treeLeft, mid);
	int rightIdx = findHeightIdx(start, end, node * 2 + 1, mid + 1, treeRight);

	if (leftIdx == -1 || rightIdx == -1)
		return max(leftIdx, rightIdx);
	
	return histogram[leftIdx] <= histogram[rightIdx] ? leftIdx : rightIdx;

}



int getArea(int start, int end) {
	if (start > end)
		return -1;

	int minIdx = findHeightIdx(start, end, 1, 0, n - 1);

	int res = (end - start + 1) * histogram[minIdx];

	//시작이 최소 인덱스가 아니여야 나눌 수 있다.
	if (start != minIdx)
		res = max(res, getArea(start, minIdx - 1));
	if (end != minIdx)
		res = max(res, getArea(minIdx + 1, end));

	return res;
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	cin >> n;
	tree.resize(n * 4);

	for (int i = 0; i < n; i++) {
		cin >> histogram[i];
	}

	init(0, n - 1, 1);
	cout << getArea(0, n - 1);
}

코멘트

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

import java.io.*;
import java.util.*;

/**
 * 14:30 시작!  
 */
public class Main
{
    /**
     * 예전에 풀었던 문제랑 비슷! => 해당 문제는 그리디
     * n은 최대 100_000
     * 높이는 최대 1_000_000_000
     * 
     * 어렵다.. 투포인터를 생각해 봤는데..
     * 알고리즘 분류를 보니, 세그먼트 트리!
     */
    static int n;
    static int[] heights, tree;
	public static void main(String[] args) throws Exception {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	    n = Integer.parseInt(bf.readLine());
	    heights = new int[n + 1];
	    
	    // 1. 입력 받기
	    for(int i = 1; i <= n; ++i) {
	        heights[i] = Integer.parseInt(bf.readLine());
	    }
	    
	    //         1
	    //     1      3
	    //  1   4   3  3
	    // 2 1 4 5 3 3 
	    
	    //         1
	    //     1      4
	    //  1   2   4  6
	    // 0 1 2 3 4 5 
	    
	    // 2. 세그먼트 트리
	    tree = new int[n * 4];
	    initTree(1, n, 1);
	    
	    System.out.println(findMaxArea(1, n));
	}
	
	public static int initTree(int start, int end, int node) {
	    if(start == end) return tree[node] = start;
	    
	    int mid = (start + end) / 2;
	    int leftIdx = initTree(start, mid, node * 2);
	    int rightIdx = initTree(mid + 1, end, node * 2 + 1);
	    
	    return tree[node] = (heights[leftIdx] > heights[rightIdx]) ? rightIdx : leftIdx;
	}
	
	// start ~ end 범위 사이의 최대 넓이
	public static int findMaxArea(int start, int end) {
	    int idxOfMin = getIdxOfMin(1, n, 1, start, end);
	    int result = heights[idxOfMin] * (end - start + 1);
	    
	    if(start < idxOfMin) result = Math.max(result, findMaxArea(start, idxOfMin - 1));
	    if(idxOfMin < end) result = Math.max(result, findMaxArea(idxOfMin + 1, end));
	    
	    return result;
	}
	
	// left와 right 사이에 가장 작은 높이의 인덱스
	public static int getIdxOfMin(int start, int end, int node, int left, int right) {
	   if(left > end || right < start) return -1;
	   if(left <= start && right >= end) return tree[node];
	   
	   int mid = (start + end) / 2;
	   int leftIdx = getIdxOfMin(start, mid, node * 2, left, right);
	   int rightIdx = getIdxOfMin(mid + 1, end, node * 2 + 1, left, right);
	   
	   if(leftIdx == -1) return rightIdx;
	   if(rightIdx == -1) return leftIdx;
	   
	   return heights[leftIdx] > heights[rightIdx] ? rightIdx : leftIdx;
	}
}

코멘트

- 투포인터, 스택 생각도 했는데 도저히 안풀려서 보니 스택 or 세그먼트 트리로 풀이 가능한 문제였습니다! 전에 푼 세그먼트 트리 문제와 다른 점은 1. 트리에 값이 아닌 값의 인덱스를 넣는다(여기서는 범위 내에 최솟값이 위치한 인덱스) 2. 트리를 탐색할 때, 부모가 기준이 아니고, 해당 구간에서 가장 작은 노드를 기준으로 분리한다.
-스택으로도 풀이 가능하다고 하니, 도전해 봐야겠습니다..!