[SW Expert Academy] D3 1208. Flatten

*쉽다고 생각하면 항상 실수하게된다.. 특히 초기화하는거ㅠ*

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

int main() {
	int dump, height;


	for (int tc = 0; tc < 10; tc++) {
		cin >> dump;
		map<int, int> box = {};
		for (int i = 0; i < 100; i++) {
			cin >> height;
			box[height]++;
		}
		
		for (int i = 0; i < dump; i++) {
			box.begin()->second--;
			box[box.begin()->first + 1]++;
			box.rbegin()->second--;
			box[box.rbegin()->first - 1]++;

			if (box.begin()->second == 0) box.erase(box.begin()->first);
			if (box.rbegin()->second == 0) box.erase(box.rbegin()->first);
			
			if (box.rbegin()->first - box.begin()->first <= 1) break;
		}
		cout<<"#"<<tc+1<<" "<<box.rbegin()->first - box.begin()->first<<endl;
	}
}

---

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

728x90

---

[접근1]

제일 높은거 높이 낮은거 높이를 쉽게 알 수 있어야한다. 따라서 같은 높이도 있을 수 있으므로 map을 사용했다.

map에 해당 높이와 그 높이만큼 쌓인 칸의 수를 세서 map에 집어넣는다.

for (int i = 0; i < 100; i++) {
    cin >> height;
    box[height]++;
}

---

[접근2]

제일 높은 것의 count 숫자를 하나 줄이고 그 높이보다 1 낮은 것의 count 숫자를 1 올린다.

제일 낮은 것의 count 숫자를 하나 줄이고 그 높이보다 1 높은 것의 count 숫자를 1 올린다.

만약 count가 0이되면 그 높이의 칸이 없다는것이므로 map에서 없애준다.

만약 제일 높은곳과 낮은곳의 차이가 1보다 작거나 같으면 평탄화 작업이 끝난것이므로 멈춘다.

for (int i = 0; i < dump; i++) {
    box.begin()->second--;
    box[box.begin()->first + 1]++;
    box.rbegin()->second--;
    box[box.rbegin()->first - 1]++;

    if (box.begin()->second == 0) box.erase(box.begin()->first);
    if (box.rbegin()->second == 0) box.erase(box.rbegin()->first);

    if (box.rbegin()->first - box.begin()->first <= 1) break;
}