1946 신입사원

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read =sys.stdin.readline
T = int(read())
result_array = []
for _ in range(T):
    N = int(read())
    array = []
    for _ in range(N):
        x,y = map(int,read().split())
        if x == 1 : interview = [x,y]
        else : array.append([x,y])
    array.sort()
    cnt = 1
    for i in range(N-1):
        now = array[i]
        if now[1] < interview[1] and now[0]>interview[0]:
            cnt += 1
            interview = now
    result_array.append(cnt)

for m in range(T):
    print(result_array[m])

3. 생각 및 풀이

생각

그리디는 항상 아이디어가 중요하다. 잘 생각하자. 근데 백준의 채점 결과 소요시간이 많이 걸려서.. 효율적으로 코드를 짠 것 같진 않다.

풀이

이 문제는 나같은 경우엔 먼저 서류성적 순으로 나열을 했다. 그 이유는 어차피 서류 1등을 제외한 다음 순번들은 서류에서 자신보다 높은 순위의 사람이 항상 존재하기 때문에 면접만 바라보면 되기 때문.

그래서 면접대상들을 한명씩 추출해서 현재의 비교 대상과 면접순위를 비교한다. 비교한 후에 면접 순위가 더 높으면 카운트를하고 비교 대상을 갱신한다. 이렇게 해도 되는 이유가, 채용되려면 서류에선 이미 밀렸으니 면접에선 누군가보단 더 커야하는데, 항상 비교 대상의 면접 순위는 현재 나온 사람들 중 가장 높은 순위이므로 이보다 더 큰 사람이 나오게 되면 그 사람으로 면접 순위를 갱신하여 가장 높은 순위를 항상 유지하기 때문이다.