[그리디] 코딩테스트 문제 TIL (신입 사원) - 백준 1946번

1. 오늘의 학습 키워드

• 정렬
• 그리디 알고리즘

---

2. 문제: 1946. 신입 사원

• 단계: 🥈실버 1단계
• 주제:
  • 그리디 알고리즘
  • 정렬
• 출처: https://www.acmicpc.net/problem/1946

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

예제 출력 1 복사

4
3

---

3. 문제 풀이

Step1. 문제 이해하기

지원자의 서류 심사 순위와 면접 순위가 주어질 때, 두 순위 중 하나라도 다른 지원자보다 뒤쳐지지 않는 지원자를 선발합니다.

즉, 한 지원자의 순위가 다른 지원자보다 서류 심사와 면접 모두 낮은 경우에는 선발 되지 않습니다.

이러한 조건을 만족시키면서, 선발할 수 있는 신입사원의 최대 인원수를 구해야 합니다.

우선, 입출력을 살펴보겠습니다.

• Input:
  • 첫째 줄에는 테스트 케이스의 개수 T가 주어지며 1이상 20이하입니다.
  • 각 테스트 케이스의 첫째 줄에는 지원자의 숫자가 주어집니다. 지원자의 숫자는 1이상 $10^5$이하입니다. 이것이 시간 복잡도에 영향을 줄 것으로 예상되는데 $O(n^2)$보다 효율적인 시간 복잡도로 코드를 구성해야 합니다.
  • 둘째 줄부터 N(지원자의 수)개 줄에는 각각의 지원자의 서류 심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어집니다.
• Output:
  • 각 테스트 케이스에 대해서 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

step2. 문제 분석하기

선발 조건에 심사되는 점수는 두 항목 서류 심사와 면접 심사가 있습니다.

두 순위 중 하나라도 다른 지원자보다 뒤쳐지지 않는 지원자를 선발해야 하는 상황입니다.

즉, 두 항목 중 한 항목을 정렬한다면 나머지 항목에서 앞쪽에 있는 지원자들만 고려하면 됩니다.

정리하자면 다음과 같습니다.

1. 정렬:
   • 서류 심사 순위(면접 심사여도 됩니다)를 기준으로 오름차순으로 정렬합니다.
   • 이렇게 정렬하면 서류 심사 순위에서 앞쪽에 있는 지원자들만 고려하면 됩니다.
   • 이후 면접 순위만 비교하면 됩니다.
2. 그리디 조건:
   • 서류 심사 순위를 기준으로 정렬한 후, 면접 순위에서 이전까지의 최솟값보다 높은 지원자는 선발하지 않습니다.
   • 이를 통해 면접 순위를 기준으로 다른 지원자보다 뒤쳐지지 않는 지원자만 선발할 수 있습니다.

Step3. 코드 설계

1. 입력 데이터 처리:
   • 각 테스트 케이스에 대해 지원자 정보를 입력받고 서류 심사 순위 기준으로 정렬합니다.
2. 선발 조건 확인:
   • 서류 순위가 앞선 순서대로 확인하면서, 현재까지의 면접 순위 최솟값을 갱신합니다.
   • 현재 지원자의 면접 순위가 이 최솟값보다 작으면 선발합니다.
3. 결과 출력:
   • 각 테스트 케이스의 최대 선발 인원을 출력합니다.

Step4. 코드 구현

import sys
T = int(sys.stdin.readline().strip())
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    scores = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    scores.sort()
    
    cnt = 1
    max_score = scores[0][1]
    for i in range(1, N):
        if max_score > scores[i][1]:
            cnt += 1
            max_score = scores[i][1]
    print(cnt)

• 코드 설명:
  • 입력 처리:
    • 테스트 케이스 개수 T를 입력받습니다.
    • 각 테스트 케이스마다 지원자 N명과 그들의 서류, 면접 순위를 입력받습니다.
  • 정렬:
    • 서류 심사 순위를 기준으로 오름차순 정렬합니다. 이렇게 하면 서류 심사에서 이미 앞선 순위의 지원자만 고려하면 되므로 면접 순위만 비교하면 됩니다.
  • 선발 조건 확인:
    • 서류 심사에서 가장 앞선 지원자는 무조건 선발되므로 cnt=1로 초기화합니다.
    • 이후, 현재까지 선발된 지원자 중 면접 순위의 최솟값을 유지하며 max_score를 갱신합니다.
    • 현재 지원자의 면접 순위가 max_score보다 낮으면 선발하고, 최솟값을 갱신합니다.
  • 결과 출력:
    • 각 테스트 케이스의 최대 선발 인원을 출력합니다.
• 시간 복잡도:
  • 정렬: 각 테스트 케이스에서 N명의 지원자를 정렬하므로 $O(N \log N).$
  • 선발 과정: 정렬된 데이터를 순회하며 선발 조건을 확인하므로 $O(N)$.
  • 따라서, 각 테스트 케이스의 시간 복잡도는 $O(NlogN)$, 전체 시간 복잡도는 $O(T \cdot N \log N)$.
• 결과:
  

---

4. 마무리

이 문제는 서류 심사 순위로 정렬한 후 면접 순위를 비교하는 그리디 알고리즘 문제입니다. 정렬을 통해 한 항목을 기준으로 제한을 두어 문제를 단순화하고, 나머지 항목만 비교하여 조건을 만족시키는 방식으로 효율적인 풀이가 가능했습니다. 특히, $O(N \log N)$의 시간 복잡도로도 N이 최대 100,000까지 가능하기 때문에 제한 시간 내에 해결할 수 있습니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!