화투의 개발 블로그

문제 링크

이렇게 로직 생각을 하고 처음에 코드를 작성하였다. 

#include <cstdio>
#include <algorithm>
int t,n,rank[100000][2],r1,r2;
int recruit(){
    //정렬한다. 
    for(int i = 0; i<n; i++){
        for(int j= 1;j<n-i;j++){
            if(rank[j][0]<rank[j-1][0]){
                std::swap(rank[j][0],rank[j-1][0]);
                std::swap(rank[j][1],rank[j-1][1]);
            }
        }
    }
    
    int min = rank[0][1],count = 1;;
    for(int i=0;i<n;i++){
        if(min>rank[i][1]){
            count++;
            min = rank[i][1];
        }
    }   
    return count;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        //각 사원의 등수 입력 
        for(int i =0; i<n;i++){
            scanf("%d %d",&rank[i][0],&rank[i][1]);
        }
        printf("%d\n",recruit());
    }
}

정렬은 그냥 편하게 버블 소트로 하였더니 시간 초과가 발생하였다. 이를 해결하려고 퀵소트로 바꿔서 다시 정렬을 해보았으나. 이 또한 시간 초과가 발생하였다. 

그러면 입력을 받은 후 정렬을 하는 것이 아니라, 입력 도중에 정렬을 할 필요가 있었다. 고민하던 차에 ,이 문제에서 애초에 '1위부터 N위까지 동석차 없이 결정된다고 가정'했으므로, 그냥 등수에 맞는 배열의 인덱스에다가 저장하면 될 일이었다. 

#include <cstdio>
using namespace std;
int t,n,rank[100001],rx,ry;
int recruit(){
    int min = rank[1],count = 1;
    for(int i=1;i<=n;i++){
        if(min>rank[i]){
            count++;
            min = rank[i];
        }
    }   
    return count;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        //각 사원의 등수 입력 
        for(int i =0; i<n;i++){
            //서류점수 등수 순서대로 면접 점수를 입력받는다. 
            scanf("%d %d",&rx,&ry);
            rank[rx] = ry; 
        }
        printf("%d\n",recruit());
    }
}

그렇게 코드를 다시 작성하였다. 다른 사람들의 코드를 보니 이 방법이나, 정렬 코드를 짜는 것이 아닌 STL의 sort를 통한 정렬은 시간 초과 없이 작동하는 것 같았다.

아마 테스트케이스중에 완전 역순으로 정렬된 테스트케이스가 있어 정렬에 n^2이 걸렸기 때문인 것 같았다. 이 경우에 대한 처리나 머지소트로 정렬했으면 시간초과가 안날것 같기는 하다.

어려운 문제는 아니었지만 너무 틀에 박힌 생각보다는 좀 더 폭넓게 생각하는 버릇이 필요한 것 같다는 생각이 든다..