99클럽 코테 스터디 _ 19일차 TIL (그리디)

 

< 문제 >

[백준] 1946. 신입 사원 / 실버1

---

< 풀이 >

코드 변수 정의

• applicants : 입력받은 지원자 정보를 저장하는 리스트
• max_new : 선발할 수 있는 신입사원의 최대 인원수
• b : 지원자의 면접 성적
• min_b : 현재 지원자까지의 최소 면접 성적   *초기 값은 무한대 값으로 초기화한다.

---

Greedy
시간복잡도 : O(N logN)

def recruit():
    N = int(input())
    applicants = [list(map(int, input().split())) for _ in range(N)] # 지원자 정보 저장 리스트
    applicants.sort()

    max_new = 0 # 선발 가능 최대 인원수
    min_b = float('inf') # 최솟값을 무한대 값으로 초기화

    for _, b in applicants: # b : 면접 성적
        if b < min_b:  # 현재 b가 지금까지의 최소값보다 작으면 새로운 그룹 가능
            max_new += 1
            min_b = b  # 최소값 업데이트

    return max_new

def main():
    T = int(input()) # 테스트 케이스 수
    for _ in range(T):
        print(recruit())

if __name__ == "__main__":
    main()

 

 

 

 

풀이 방식

1. 지원자 정보 정렬
   • 지원자의 서류심사 성적을 기준으로 오름차순 정렬을 한다.
   • 서류심사 성적이 같으면 면접시험 점수도 오름차순으로 정렬된다.
   • applicants 정렬 후 결과 예시
     • 문제 예제 입력 1 중 첫 번째 testcase를 예시로
     • applicants = [[3,2], [1,4], [4,1], [2,3], [5,5]]
       
       

       서류심사 성적	면접시험 성적
       1	4
       2	3
       3	2
       4	1
       5	5

2. 선발 가능 신입사원 최대 인원수 계산
   • 정렬된 상태에서 서류심사 성적은 항상 증가하므로, 면접시험 성적만 고려하면 된다.
   • 현재 면접 성적이 min_b보다 작다면, 선발할 수 있다.
     • 최대 인원수 변수인 max_new에 +1을 해준다.
     • min_b값을 현재 면접 성적으로 업데이트한다.
   • 실행 과정 결과는 다음 표와 같이 나타낼 수 있다.
     
     

     현재 b(면접시험 성적) 값	min_b	포함 여부	max_new
     4	∞	O	1
     3	4	O	2
     2	3	O	3
     1	2	O	4
     5	1	X	4

---

< 회고 >

🤔 💭_

문제에서 '서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발' 한다고 나와있어서 2개의 성적 중 하나의 성적을 오름차순으로 정렬하고 나머지 하나의 성적을 비교하면 되겠다고 생각하고 풀었다.

서류심사 성적을 기준으로 오름차순 정렬 후 순서대로 면접시험 성적을 비교했을 때 면접시험 성적이 내림차순을 갖는다면 모든 지원자가 둘 중의 한 성적이 다른 지원자에 비해 큰 값을 갖게 된다.

지원자 정보 정렬 후 한 번의 순회로 문제를 해결할 수 있기 때문에 작은 시간복잡도로 매우 효율적으로 풀이할 수 있다.