반응형
문제링크:https://www.acmicpc.net/problem/10825
10825번: 국영수
첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.
www.acmicpc.net
그리디 알고리즘입니다. (사실 그리디라고도 할 수 없는 단순 정렬문제)
algorithm 라이브러리에 sort함수를 구현해 해결했습니다.
cmp는 오버라이딩 된 형태라 직접 구현할 수 있습니다.
주석에 써놓은 번호순서대로 문제에서 요구하는 정렬을 구현한 것입니다.
bool cmp(info a, info b) {
if (a.korean > b.korean) //1
return true;
else if(a.korean == b.korean){
if (a.english < b.english) return true; //2
else if(a.english == b.english){
if (a.math > b.math) return true; //3
else if(a.math == b.math) {
if (a.name < b.name)return true; //4
}
}
}
return false;
}
처음에 시간초과가 났습니다. n = 100000 이고 sort 함수를 O(nlgn) 이기때문에 정렬의 문제는 아니였습니다.
endl << 이 너무 많은 시간을 잡아먹어서 에러가 났었습니다. endl는 버퍼를 flush하는 역할을 겸하기 때문에 위 처럼 많은 출력을 해야해서 endl이 많이 사용될때는 endl사용을 지양하고 '\n'을 사용해야 합니다.
정답코드입니다.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct info {
string name;
int korean;
int english;
int math;
};
info arr[100001];
int n = 0;
/*
국어 점수가 감소하는 순서로
국어 점수가 같으면 영어 점수가 증가하는 순서로
국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)
*/
bool cmp(info a, info b) {
if (a.korean > b.korean) //1
return true;
else if(a.korean == b.korean){
if (a.english < b.english) return true; //2
else if(a.english == b.english){
if (a.math > b.math) return true; //3
else if(a.math == b.math) {
if (a.name < b.name)return true; //4
}
}
}
return false;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i].name >> arr[i].korean >> arr[i].english >> arr[i].math;
sort(arr, arr + n, cmp);
for (int i = 0; i < n; i++)
cout << arr[i].name <<'\n';
}
꼭 직접 작성해보시기 바랍니다:) 화이팅
반응형
'알고리즘 > 그리디 알고리즘' 카테고리의 다른 글
| [백준] 1493-박스채우기(C++) (0) | 2020.05.19 |
|---|---|
| [백준] 1092-배(C++) (0) | 2020.05.05 |
| [백준] 8980-택배(C++) (0) | 2020.03.05 |
| [백준] 1969-DNA(C++) (0) | 2020.03.03 |
| [백준] 2437-저울(C++) (0) | 2020.03.03 |
