[G4] 백준 14411번 합집합 C++ 스택, 정렬

리뷰

 

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

간만에 머리쓰게만든 스택 문제

 

 

전역 변수

• Pos : 사각형의 크기와 높이를 정의할 구조체, 높이를 기준으로 내림차순 정렬한다.
• N : 배열의 최대 크기를 정의할 상수 변수
• arr : 사각형의 너비와 높이를 저장할 Pos타입 배열

 

함수

없음

 

 

문제풀이

1. 변수 n을 초기화 하고, n에 값을 입력받는다.
2. n개의 사각형의 너비와 높이를 입력 받아 arr배열을 초기화한다.
3. sort함수를 통해 arr배열을 높이를 기준으로 내림차순 정렬한다.
4. 변수 sum을 가장 첫 사각형의 크기로 초기화한다.
5. 변수 mxx를 가장 첫 사각형의 너비로 초기화한다.
6. 두번째 사각형부터 n번째 사각형까지 순회하는 for문을 개행한다.
7. 변수 x, y에 현재 사각형의 너비와 높이를 저장한다.
8. 변수 y_diff를 이전 사각형의 높이와 현재 사각형의 높이의 차로 저장한다.
9. mxx가 x보다 작을 경우 sum에 현재 사각형의 너비와 이전 사각형의 너비의 차와 y를 곱한 값을 더해주고, mxx를 x로 변경해준다.
10. 모든 탐색을 마친 후 sum에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 너비와 높이 중 하나를 기준으로 잡고 내림차순 정렬해준다.
2. 정렬하지 않은 다른 기준의 최대값이 갱신될때마다 너비 업데이트 처리, 최대값을 갱신해준다.

 

정답 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct Pos {
	int x, y;
	bool operator<(const Pos& other) const {
		return y > other.y;
	}
};
const int N = 1e6;
Pos arr[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, y; cin >> x >> y;
		arr[i] = { x, y };
	}
	sort(arr, arr + n);
	
	long long sum = 1ll * arr[0].x * arr[0].y;
	int mxx = arr[0].x;

	for (int i = 1; i < n; ++i) {
		auto [x, y] = arr[i];
		int y_diff = arr[i - 1].y - arr[i].y;

		if (mxx < x) {
			sum += 1ll * (x - mxx) * y;
			mxx = x;
		}

		//cout << x << " " << y << " " << sum << "\n";
	}
	
	cout << sum;
}