1946번: 신입 사원 / silver 1 / 그리디, 정렬

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

1946번: 신입 사원

- 시간 초과

'''
1946번: 신입 사원 / silver 1 / 
'''
import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    applicant = []
    for _ in range(N):
        x, y = map(int, input().split())
        applicant.append([x, y])
    applicant.sort(key=lambda x: x[0])
    i = 1
    score = applicant[0][1]
    while i < len(applicant):
        if score > applicant[i][1]:
            score = applicant[i][1]
            i += 1
        else:
            applicant.pop(i)
    applicant.sort(key=lambda x: x[1])
    i = 1
    score = applicant[0][0]
    while i < len(applicant):
        if score > applicant[i][0]:
            score = applicant[i][0]
            i += 1
        else:
            applicant.pop(i)
    print(len(applicant))

 

- 정답

'''
1946번: 신입 사원 / silver 1 / 그리디, 정렬
'''
import sys

input = sys.stdin.readline

T = int(input())
# 테스트 케이스 T 횟수 만큼 반복
for _ in range(T):
    # 지원자 수 N 입력 받기
    N = int(input())
    # 지원자 [서류, 면접] 등수 applicant 리스트에 담기
    applicant = []
    for _ in range(N):
        x, y = map(int, input().split())
        applicant.append([x, y])
    # 지원자 서류 등수로 오름차순 정렬
    applicant.sort(key=lambda x: x[0])
    # 선발되지 않는 사람 cnt
    score = applicant[0][1]
    cnt = 0
    for i in range(1, N):
        if score < applicant[i][1]:
            cnt += 1
        else:
            score = applicant[i][1]
    # 선발인원 출력하기
    print(N - cnt)

코드 리뷰

- 처음에 짠 코드의 로직은 다음과 같습니다. 

(1-1) 지원자를 서류 등수로 오름차순 한다.

(1-2) 면접 등수를 하나씩 확인하여 선발 되지 않을 경우 해당 지원자를 pop한다.

(2-1) 지원자를 면접 등수로 오름차순 한다.

(2-2) 서류 등수를 하나씩 확인하여 선발 되지 않을 경우 해당 지원자를 pop한다.

 

- 시간초과 판정을 받고 범위를 확인했을 시, 지원자를 확인하는 부분의 반복문이 한번만 나와야 되겠다고 생각했습니다.

- 다시 생각해보니 처음 짠 코드의 로직 (1-1, 1-2) 부분에서 선발 되지 않는 지원자가 모두 추려진다는 것을 알게 되었고,

- 당연히 로직 (2-1, 2-2) 는 무의미 하다고 판단하여 코드를 삭제 했습니다.

- 또한, 선발 되지 않는 지원자를 / 리스트에서 pop 하는 코드를 -> cnt 를 세는 방식으로 수정했습니다. (pop 을 할 시, 시간 복잡도 생각)