[백준 10825] 국영수

알고리즘 문제풀이/백준

[백준 10825] 국영수

홍시홍 2020. 1. 9. 21:55

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

10825번: 국영수

첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

www.acmicpc.net

1/8일 풀었던 문제

요구사항

1. 국어, 영어, 수학 순으로 정렬

풀이

머지소트 정렬

#include <stdio.h>
#include <algorithm>
#include <list>
#include <iostream>

using namespace std;
 
struct go {
    int kor;
    int eng;
    int math;
    char name[11];
    int len;
};
int chlen(char ch[]){
    int i=0;
    while(ch[i]){
        i++;
    }
    return i;
}
int n;
go map[100001];
go buf[100001];
void merge_sort(go arr[], int len){
   // cout<<"A"<<endl;
    if(len<2){
        return;
    }
    int i,j,mid,k;
    i=0;
    mid=len/2;
    j=mid;
    k=0;
    merge_sort(arr,mid);
    merge_sort((arr+mid),(len-mid));

    while(i<mid && j<len){
        if(arr[i].kor <arr[j].kor){
            buf[k++]=arr[j++];
        }
        else if(arr[i].kor == arr[j].kor){
            if(arr[i].eng < arr[j].eng){
                buf[k++]=arr[i++];
            }
            else if(arr[i].eng==arr[j].eng){
                if(arr[i].math < arr[j].math){
                    buf[k++]=arr[j++];
                }
                
                else if(arr[i].math == arr[j].math){
                    for(int l =0 ; arr[i].name[l] !=0 ; l++){
                        if(arr[i].name[l] < arr[j].name[l]){
                            buf[k++]=arr[i++];
                            break;                            
                        }
                        else if(arr[i].name[l] == arr[j].name[l] ){
                            continue;
                        }
                        else{
                            buf[k++]=arr[j++];
                            break;
                        }
                    }
                }
                
                else{
                    buf[k++]=arr[i++];
                }
            }
            else{
                buf[k++]=arr[j++];
            }
        }
        else{
            buf[k++]=arr[i++];
        }

    }

    while(i<mid){
        buf[k++]=arr[i++];
    }
    while(j<len){
        buf[k++]=arr[j++];
    }
    for(int a=0 ; a<len; a++){
        arr[a]=buf[a];
    }


}

int main(){
    cin>>n;
    for(int i=0 ; i < n ; i++){
        scanf(" %s %d %d %d",&map[i].name,&map[i].kor,&map[i].eng,&map[i].math);
        map[i].len=chlen(map[i].name);
    }
    merge_sort(map,n);
 //   cout<<endl;
    for(int i=0 ; i < n ; i++){
        printf("%s\n",map[i].name);
    }
}