[백준 1946] 신입 사원 (python)

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

1946번: 신입 사원

신입 사원 문제

성적, 서류 등수가 다른 지원자보다 떨어지면 탈락이고, 그렇지 않으면 합격일 때 최대 가능한 합격자 수를 구해보자.

 

⚙️내가 푼 정답코드

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    rank = sorted([list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]) # 서류를 기준으로 정렬
    cnt = 1
    second_rank = rank[0][1]
    for i in range(1,N):
        if rank[i][1] < second_rank: # 면접 순위가 이전사람들보다 높으면
            cnt += 1 # 횟수 증가
            second_rank = rank[i][1]
    print(cnt)

반응형

📌문제 접근 포인트

1. 한쪽을 기준으로 먼저 정렬을 먼저하면 나머지는 찾기 쉬워지니 정렬을 먼저 해보자.
2. 정렬을 완료했다면 0번 인덱스의 두번째 요소를 기준으로 잡아주고, 이 숫자와 비교해가면서, 하나씩 카운트하면 쉽게 구할 수 있다.
3. sort를 적용하므로, 처리시간이 굉장히 오래걸리는 단점이 있지만, 이렇게 그리디 알고리즘으로 해결 가능하다!