백준 10825 국영수 c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 시간초과 오류가 떴다.

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

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);
    int n;
    cin >> n;
    
    vector<string> name(100001);
    vector<int> korean(100001); vector<int> english(100001); vector<int> math(100001);
    for(int i=1; i<=n; i++){
        cin >> name[i] >> korean[i] >> english[i] >> math[i];  
    }
    
    string temp;
    int temp1; int temp2; int temp3;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j)
                continue;
            else if(korean[i] < korean[j]) {
                //1. 국어 점수가 감소하는 순서로
                temp = name[i]; temp1 = korean[i]; temp2 = english[i]; temp1 = math[i];
                name[i] = name[j]; korean[i] = korean[j]; english[i] = english[j]; math[i] = math[j]; 
                name[j] = temp; korean[j] = temp1; english[i] = temp2; math[i] = temp3; 
            }
            else if(korean[i] == korean[j] && english[i] == english[j] && math[i] == math[j]) {
                //4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로
                if(name[i] > name[j]) {
                    temp = name[i]; temp1 = korean[i]; temp2 = english[i]; temp1 = math[i];
                    name[i] = name[j]; korean[i] = korean[j]; english[i] = english[j]; math[i] = math[j]; 
                    name[j] = temp; korean[j] = temp1; english[i] = temp2; math[i] = temp3;                     
                }                
            }
            else if(korean[i] == korean[j] && english[i] == english[j]) {
                //3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
                if(math[i] < math[j]) {
                    temp = name[i]; temp1 = korean[i]; temp2 = english[i]; temp1 = math[i];
                    name[i] = name[j]; korean[i] = korean[j]; english[i] = english[j]; math[i] = math[j]; 
                    name[j] = temp; korean[j] = temp1; english[i] = temp2; math[i] = temp3;                     
                }
            }
            else if(korean[i] == korean[j]){
                //2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
                if(english[i] > english[j]) {
                    temp = name[i]; temp1 = korean[i]; temp2 = english[i]; temp1 = math[i];
                    name[i] = name[j]; korean[i] = korean[j]; english[i] = english[j]; math[i] = math[j]; 
                    name[j] = temp; korean[j] = temp1; english[i] = temp2; math[i] = temp3;                     
                }                
            }
        }
    }
    
    for(int i=1; i<=n; i++)
        cout << name[i] << "\n";
    
    return 0;
}

 

 

 

algorithm 헤더의 sort함수를 알고는 있었으나 이렇게 단순 정렬이 아닌 조건이 달린 상황에서 어떻게 사용할 지 몰라 그냥 for문으로 정렬을 구현한 것이었다.

하지만 sort함수의 세번째 인자에 cmp함수를 추가하여 쉽게 구현할 수 있었고, 구조체 형태로 선언한 한 벡터안에 4가지 값을 모두 저장하여 더 빠르게 계산되도록 할 수 있었다.

다시 작성한 코드는 다음과 같다.

(주의)

문제에서 배열을 최대값 100001 이런식으로 선언해야 되는게 있고 n만큼만 선언해야되는 경우가 있고,

 1~n으로 해도 되는 경우가 있고 0부터 n-1까지로 둬야하는 경우가 있고

cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); 를 꼭 해줘야하는 경우가 있고 

다 다르므로 다 고려해주자.

보통 dp문제는 전자고 정렬 문제는 후자가 필요한 것 같긴 한다.

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

struct STU{
    string name;
    int korean, english, math;
};

bool cmp(STU a, STU b) {
    //4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로
    if (a.korean == b.korean && a.english == b.english && a.math == b.math) 
        return a.name < b.name; //-> 원하는 정렬대로 return
    //3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
    if (a.korean == b.korean && a.english == b.english) 
        return a.math > b.math;
    //2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
    if (a.korean == b.korean) 
        return a.english < b.english;
    //1.국어 점수가 감소하는 순서로 => 이걸 기본으로 두기
    return a.korean > b.korean;
}    

int main(){
    int n;
    cin >> n;
    
    vector<STU> v(n);
    for(int i=0; i<n; i++){
        cin >> v[i].name >> v[i].korean >> v[i].english >> v[i].math;  
    }
    
    sort(v.begin(), v.end(), cmp);
    
    for(int i=0; i<n; i++)
        cout << v[i].name << "\n";
    
    return 0;
}