#1946 신입 사원

문제 정리

1차 서류, 2차 면접. 최고의 인재들만 선발
다른 모든 지원자와 비교했을 때 1차, 2차 중 적어도 하나라도 다른 모든 지원자보다 점수가 높은 사람만 선발.
(= A가 B의 성적에 비해 1차, 2차 다 낮다면 A는 절대 선발 X)
동석차 없음, 각 테스트 케이스에 대해서 선발 가능한 신입사원의 최대 수 한 줄에 하나씩 출력

생각해보기

숫자가 작은게 1등이다.
1차 기준으로 다 정렬해놓고 1차에서 1등인 애의 2차 등수보다 더 작은 등수 가진 애만 카운트하기!

아니 1차 기준으로 정렬 할 필요도 없지!!! 그냥 1등인 애의 2차 등수 뽑아서 2차 등수 더 높은 애만 카운트 하면 되네
1차에서 1등인 애의 2차 등수는 입력받을 때 저장해 놓기. (전체 탐색하는 일 없도록)
1등인 애의 2차 등수 받고 나서는(0이 아니면) 입력받을 때 검사 바로바로 해서 벡터에 push_back()도 안 시키면
더 검사 수가 줄 듯 하다..

아니다… 1등한테 2차는 이긴 애들끼리도 비교해야 되잖아…?

그러면 다시 생각해보자. 그리디로?
우선 1차에서 1등한 애 먼저 뽑고, 그 1등에게 2차를 이긴 애들을 카운트한다. (그리고 뺀다)
그 다음 남은 애들 중에서 1등한 애 뽑고, 그 1등에게 2차를 이긴 애들을 카운트..? 해도 되나? 안됨.

그럼 우선 아니다… 까지 해 놓고, 그 후에 1차 기준으로 정렬하고 (??ㅠㅠ아 굳이 해야되나?)
밑으로 내려가면서 2차를 비교해보자.

코드 쓰기

오조오억번의 시간초과 그 후…
입력받을 때 거를 거 거르고 1차 등수대로 정렬해놓은 후,
i번째 지원자는 1~i-1 지원자보다 2차만 잘 봤으면 합격이다.

그러므로1~i-1 2차 등수 중 최솟값을 min 변수에 저장해 놓고
i번째 지원자가 합격인지 아닌지 비교하면 된다! 휴~

내 풀이

// BOJ-1946 신입 사원
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct pair<int, int> Score;

int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    // 테스트 케이스 수
    int testCase = 0;
    cin >> testCase;

    // 테스트 케이스 수 만큼 반복
    for (int i=0; i<testCase; i++){
        int answer = 0, person = 0, best = 0;
        vector<pair<int, int> > v;
        
        // 사원 수 입력
        cin >> person;
        // 사원들 점수 입력
        for(int k=0; k<person; k++){
            pair<int, int> s;
            cin >> s.first >> s.second;

            // best 점수가 있을 시 그 후로는 바로 검사
            if (best != 0){
                if(s.second < best){
                    v.push_back(s);
                }
            }else {
                // best 점수가 없으면 그냥 push
                v.push_back(s);
            }

            // 1차에서 1등의 2차 점수 저장
            if (s.first == 1){
                best = s.second;
            }
        }
        
        // 1차 1등보다 2차 성적 안 좋은 애들 빼기
        for (int k=0; k<v.size(); k++){
            if (v[k].second > best) {
                v.erase(v.begin() + k);
            }
        }

        // 1차 시험 등수 기준으로 벡터 정렬
        sort(v.begin(), v.end());
        answer++; //1차 시험 1등

        int min = v[0].second;

        for(int k=1; k<v.size(); k++){
            
            if (v[k].second < min){
                min = v[k].second;
                answer++;
            } 

            if (v[k].second == 1){
                break;
            }
        }

        // 정답 출력
        cout << answer << endl;
    }
}

풀고 나서 알게된 것

 cin.tie(NULL); cout.tie(NULL);
 ios_base::sync_with_stdio(false);

이 문제처럼 입력이 많은 문제의 경우에는 입력하다가도 시간초과가 날 수 있다고 한다.
그래서 위에 코드를 써줘서 스트림을 분리(?)해 줘야 한다고 한다!~

오답 노트

// BOJ-1946 신입 사원
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct pair<int, int> Score;

int main() {
    // 테스트 케이스 수
    int testCase = 0;
    cin >> testCase;

    // 테스트 케이스 수 만큼 반복
    for (int i=0; i<testCase; i++){
        int answer = 0, person = 0, best = 0;
        vector<pair<int, int> > v;
        
        // 사원 수 입력
        cin >> person;
        // 사원들 점수 입력
        for(int k=0; k<person; k++){
            pair<int, int> s;
            cin >> s.first >> s.second;

            // best 점수가 있을 시 그 후로는 바로 검사
            if (best != 0){
                if(s.second < best){
                    v.push_back(s);
                }
            }else {
                // best 점수가 없으면 그냥 push
                v.push_back(s);
            }

            // 1차에서 1등의 2차 점수 저장
            if (s.first == 1){
                best = s.second;
            }
        }

        // 1차 1등보다 2차 성적 안 좋은 애들 빼기
        for (int k=0; k<v.size(); k++){
            if (v[k].second > best) {
                v.erase(v.begin() + k);
            }
        }

        // 1차 시험 등수 기준으로 벡터 정렬
        sort(v.begin(), v.end());

        while(!v.empty()){
            v.erase(v.begin()); // 1등꺼 뺌
            answer++;

            best = v[0].second;
            for(int j=1; j<v.size(); j++){
                if (best <= v[j].second){
                    v.erase(v.begin() + j);
                }
            }
        }
        
        cout << answer;
    }
}

또 시간초과… 검사 수가 너무 많아서 그런 것 같기도 하다. 지원자의 수가 최대 10만이기 때문에!….ㅠ__ㅠ
그래서 입력때 거른다고 거른건데… 테스트 케이스가 20까지 될 수 있어서 더 그런 것 같다.

for(int k=1; k<v.size(); k++){
            for(int j=0; j<k-1; j++){
                if(v[k].second > v[j].second ) {
                    break;
                }
                answer++;
            }
        }

이렇게 해도 안 되고…

int min = v[0].second;

        for(int k=1; k<v.size(); k++){
            
            if (v[k].second < min){
                min = v[k].second;
                answer++;
            } 

            if (v[k].second == 1){
                break;
            }
        }

이렇게 줄였다아아아악 ㅠ___ㅠ 감격… 그 후에 *1차 1등보다 2차 성적 안 좋은 애들 빼기* for문도 지워주니까
(해줄 필요가 없어짐) 시간초과 안 뜨고 맞았습니다가 떴다.
그리고 마지막에

// 정답 출력
cout << answer << endl;

endl 해주는 것도 잊지 말기! 이거때문에 틀렸습니다도 봤다.

진짜 울고 싶었다….ㅠ뿌듯ㅠ