백준 - 1946 신입사원

문제 링크

greedy로 푸는 문제이다.

내가 풀이한 방법은 먼저 서류 등수나 면접 등수를 기준으로 오름차순 정렬을 한다

자신을 제외한 다른 모든 신입 사원과 점수를 비교해서, 무조건 적어도 하나의 항목은 다른 인원보다 높아야 하므로 두 항목 중 하나라도 1등인 지원자는 무조건 선발되기 때문에 1등에 대한 카운트 하나를 증가시켜준다. 만약 서류 등수를 기준으로 오름차순 정렬을 했으면, 서류 등수를 따라 올라가면서, 처음에 서류 1등이 가진 면접 등수보다 등수가 높은 인원을 찾는다. 만약 찾았다면 그 지원자는 서류 1등보다 서류 등수는 낮지만 면접 등수는 높으므로 선발 자격이 된다.

그리고 기준을 방금 찾은 지원자의 면접 등수로 설정하고, 그 새로 기준을 잡은 면접 점수보다 높은 사람을 찾아나간다. 애초 서류 등수 기준으로 오름차순을 했으므로, 그 뒤에 현재 기준의 면접 점수보다 등수가 높은 사람의 서류 등수는 무조건 그 전에 찾은 지원자보다 낮지만 면접 점수는 높게 되기 때문에 선발 조건을 만족할수밖에 없다. --> 즉, 정렬한 이후에는 최장증가부분수열을 찾으면 된다.

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

#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이 걸렸기 때문인 것 같았다. 이 경우에 대한 처리나 머지소트로 정렬했으면 시간초과가 안날것 같기는 하다.

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