[BOJ/C++] 1946번 : 그리디

문제 설명

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

문제 해석

우선 해당 문제를 '제대로' 이해하는 것이 중요하다.
나는 두번째 줄부터 N번째 줄 까지의 값이 서류,면접 점수라 생각하고 문제에 접근해서 테스트케이스가 이해가되지 않았다.

하지만 문제를 잘 읽어보면 서류,면접 점수의 순위이므로 이해한 바와 완전히 다른 결과가 나오는 것이 맞다.
아래 케이스를 예시로 문제를 해석해보자면 

2
5
3 2
1 4
4 1
2 3
5 5

5명의 지원자가 존재하고 각 지원자가 서류,면접에서 얻은 순위가 차례대로 입력된다.
이 때 A지원자는 A지원자를 제외한 어떤 지원자 한테든 서류 or 면접의 순위가 높아야한다.
만약 A지원자가 B 지원자에 비해 서류와 면접 둘다 낮은 순위를 얻었다면, A지원자는 합격하지 못한다.

위 예시로 A지원자를 3,2 로 둔다면 1,4 순위를 얻은 지원자보다 서류는 낮아도 면접 순위는 높기때문에 합격한다.
하지만 A 지원자를 5,5로 둔다면 1,4 순위를 얻은 지원자보다 서류, 면접 모두 낮기 때문에 불합격한다.

해당 문제를 풀기 위해 생각해낸 아이디어는 다음과 같다.

문제 풀이 아이디어

1. 서류 순위가 높은 순서대로 정렬한다.
2. 자신보다 서류 순위가 높은 사람의 면접 순위만을 나의 면접 순위와 비교한다. 
(그 외 것은 보지않는다. 나보다 서류순위가 낮은 사람과 나의 면접 순위를 비교 할 필요는 없다. 
나는 이미 나보다 서류순위가 높은 사람이 존재 or 자신이기 때문에 나보다 높은 순위의 면접 점수만 비교해 탈락 여부만 파악하면 되기 때문이다.) 

처음으로 작성한 비교 코드는 아래와 같다. (정답코드가 아님)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T, N;
    int P, M; // 서류, 면접

    cin >> T;
    for (int i = 0; i < T; i++) {
        int ans = 1;
        cin >> N;
        vector <pair<int, int>> v;
        for (int j = 0; j < N; j++) {
            cin >> P >> M;
            v.push_back(make_pair(P, M));
        }
        sort(v.begin(), v.end()); 
        
        for (int i = 1; i < N; i++) {
            int flag = 0;
            for (int j = 0; j < i; j++) {
                if (v[i].second > v[j].second) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
                ans++;
            }
        }
        cout << ans << "\n";
    }

}

 하지만 이 코드는 시간초과가 발생하였다.

1 4 o 
2 3 o
3 2 o
4 1 o 
5 5 x

정렬을 한 다음 top을 제외한 나머지 값에서 자신보다 높은 순위의 있는 지원자들을 반복문을 통해 전부 돌아보는 방식이였다. 

따라서 시간초과가 발생하지 않게, 반복문을 사용하지 않고 비교하는 방법이 무엇이 있을까 생각하게 되었다.
이 때 큐, 스택과 같은 자료구조 문제를 풀 때 사용했던 top만을 비교하는 방식이 떠올랐다.

top을 비교하자 (합격이 될 수 있는 면접 순위의 min과 비교하자)

정답코드 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T, N;
    int P, M; // 서류, 면접

    cin >> T;
    for (int i = 0; i < T; i++) {
        int ans = 1;
        cin >> N;
        vector <pair<int, int>> v;
        for (int j = 0; j < N; j++) {
            cin >> P >> M;
            v.push_back(make_pair(P, M));
        }
        sort(v.begin(), v.end()); 

        int top = v.front().second;
        for (int i = 1; i < N; i++) {
            if (top > v[i].second) {
                ans++;
                top = v[i].second;
            }
        }
        cout << ans << "\n";
    }
}

자신보다 서류 점수가 높은 지원자와만 비교하면 되기 때문에 해당 지원자의 면접 점수와 내 면접점수를 비교하는 것은 똑같다.

하지만 자신보다 서류점수가 높은 지원자가 여러명일 때 그 지원자들의 면접점수를 전부 비교하지 않고 면접 점수 중에 가장 높은 면접 점수를 기록한 사람을 기준으로 자신과 비교를 한다.

그렇게 하면 그 사람보다 높은 면접 순위를 기록했을 경우, 나보다 서류점수가 높은 다른 지원자들 보다도 면접 순위가 높은것 이므로 모두와 비교하지 않아도된다.

배운점

문제를 제대로 읽자  . . . 그리고 무작정 반복문으로 풀려고 하기보다 시간초과를 생각하면서 효율적인 방법을 찾도록 연습을 해야겠다.