코딩 테스트 연습/백준

[C++]Baekjoon 1946번: 신입 사원

jaeheon0520 2023. 12. 30. 23:05

1. 문제

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

 

1946번: 신입 사원

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성

www.acmicpc.net

 

각 지원자의 서류심사 성적, 면접 성적의 순위가 주어진다.

 

서류심사 성적, 면접 성적 둘 모두가 다른 지원자보다 낮은 지원자가 있다면,

 

그 지원자는 선발 될 수 없다.

 

이 조건을 만족시키면서 선발할 수 있는 최대 인원수를 출력하는 문제이다.

 

2. 풀이

STEP1. 각 지원자의 서류심사 성적, 면접 성적의 순위를 벡터에 받아 저장한다.

 

그리고 sort()를 활용하여 정렬을 한다.

 

sort()의 결과로 서류성적이 좋은 지원자 순으로 정렬이 될 것이다.

 

STEP2. 이 문제 해결의 핵심이 되는 부분이다.

 

서류성적이 1등인 지원자는 누구와 견주어도 뒤지지 않으므로 무조건 합격시키고(cnt = 1로 시작)

 

서류성적이 2순위인 지원자부터 상위 순위자와 면접 성적을 비교해주면 되는데,

 

서류성적 상위 순위자보다 면접 성적이 좋다면 이 지원자는 합격할 수 있다!

 

(서류는 뒤지지만 면접은 앞서기 때문)

 

서류성적 마지막 순위자까지 비교를 한 후에는 cnt를 출력해주고,

 

STEP3. 다시 cnt를 1로 초기화 한 후, 다음 테스트 케이스를 수행한다.

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

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

    int test_case; // 테스트 케이스의 횟수
    int rep; // 지원자의 숫자
    int n, m; // 지원자의 서류심사 성적, 면접 성적
    int cnt = 1; // 합격할 수 있는 인원 수(최소 1명(서류 1등)은 합격하니까 1로 초기화)
    vector<pair<int, int>> v; // 성적을 담아놓을 벡터

    cin >> test_case;

    for (int i = 0; i < test_case; i++) { // 성적 입력받아서 벡터에 저장
        cin >> rep;
        for (int j = 0; j < rep; j++) {
            cin >> n >> m;
            v.push_back(make_pair(n, m));
        }

        sort(v.begin(), v.end()); // 벡터를 정렬하면 서류심사 성적이 좋은 순으로 정렬됨

        int temp = v[0].second; // 임시로 면접 성적을 저장 할 변수

        for (int k = 1; k < rep; k++) { // 서류 2등부터 꼴등까지 반복문을 통해 비교
            if (v[k].second < temp) { // 만약 서류 k등인 사람이 상위 등수 사람보다 면접을 잘 봤다면
                cnt++; // 그 사람을 선발한다
                temp = v[k].second; // 선발 기준이 되는 면접 접수 갱신(하위 등수 후보자는 상위등수 보다 면접을 더 잘봐야 함으로 커트라인 상승)
            }          
        }
        cout << cnt << '\n';
        cnt = 1; // 다음 테스트를 위해 초기화
        v.clear(); // 다음 테스트를 위해 초기화
    }
    return 0;
}

 

4. 느낀점

나는 어떻게든 문제를 날로먹으려는 나쁜 습성이 있다.

 

지문을 잘 읽어야 한다고 문제를 풀때마다 생각하는데..

 

막상 문제를 접하면 뭔가 문제에 대해서 깊이있게 이해하고 싶어하지 않는(?) 그런 느낌이다.

 

이 문제도 역시 숫자가 높은 사람이 좋은 성적을 받은 건 줄 알고 한참 헤맸다.

 

알고보니 주어진 건 순위였고 숫자가 낮은 사람이 더 좋은 성적을 받은 것이었다.

 

그리고 한가지 더 헤멘 부분이 있다.

 

기준이 되는 면접 점수(최고 면접순위)를 temp로 설정했는데,

 

커트라인(temp)이 자꾸 올라가야 하는데(상위 순위자 보다 높은 면접 성적을 받아야 최종 합격 할 수 있으니까)

 

자꾸 내려가야 한다고 반대로 생각했었다.(즉 숫자가 작아져야 한다, 작은 숫자(순위) == 높은 점수)

 

문제를 잘 읽자! 그리고 내 생각에 틀린부분이 없는지 꼼꼼하게 검증하자!

 

아 그리고 이 문제는 그리디 알고리즘을 활용한 문제이다.

 

각 단계(해당 순위의 지원자)에서 최선의 선택(cnt)을 하기 때문이다.

 

오늘 하루도 쌓였다!