구조체
구조체란 사용자가 임의로 자료형의 집합을 하나의 데이터 형식으로 정의하는 형식이다.
sturct information {
string name;
int age;
int height;
Information(string a, int b, int c){
name = a;
age = b;
heght = c;
}
bool operator<(const Information &b)const{
return x<b.x;
}
}이렇게 구조체를 생성할 때 각 데이터의 자료형을 지정해주고, 생성자를 통해 생성될 수 있게 한다. java의 클래스와 유사한 듯 하다.
operator 부분은 구조체를 정렬하는 과정에서 사용되는 기준을 설정하는 부분이다.
75. 최대 수입 스케쥴(priority_queue 응용문제)
오늘 배운 구조체와 priority_queue를 이용해서 푸는 문제였다.
다 풀어놓고 계속 이게 왜 안돼하는 중이었는데, 데이터를 변수에 저장할 때 == 이라고 해둔 부분이 있었다. 요즘 이런 경우가 잦은데 주의해야겠다.
풀이 방식은 priority_queue를 이용해 강연료가 최대인 것을 큐의 맨 앞에 두고 요구 날짜부터 그 날짜보다 가까운 날들이 비어있는지 cnt vector로 체크하여 가능하면 더해주고 아니면 제거하는 방식으로 코드를 작성했다.
struct Schedule {
int pay;
int date;
Schedule(int a, int b){
pay = a;
date = b;
}
bool operator<(const Schedule &b)const{
return pay<b.pay;
}
};
int main(){
//freopen("input.txt","rt",stdin);
priority_queue<Schedule> pQ;
vector<int> cnt(10001,0);
int n, a, b;
cin>>n;
for(int i=0; i<n; i++){
cin>>a>>b;
pQ.push(Schedule(a,b));
}
int answer =0, tmp = 0;
while(!pQ.empty()){
int p = pQ.top().pay;
int d = pQ.top().date;
while(d>0){
if(cnt[d]==0){
cnt[d]=1;
answer+=p;
break;
}
else{
d--;
}
}
pQ.pop();
}
cout<<answer;
return 0;
}pair를 사용해도 상관없었을 것 같지만, 구조체를 사용하면 변수를 더 명확하게 다룰 수 있다는 점에서 pair보다 좋은 것 같다.
