1946 신입사원 파이썬

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

1946번: 신입 사원

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사에 관한 문제다.

 

이전에 공부했던 정렬개념의 중요성에 대해 일깨워준 문제인 것 같다.

처음에 문제 제출시에는 sort()내장 함수를 사용해서 풀었고, 풀고나서 counting sort(기수정렬)로 다시 풀어봤다.

두가지 풀이에서 시간 차이가 약 3배가까이 났다. 기수 정렬의 경우, 자료의 범위가 한정되어 있을 때, 효율적인 위력을 발휘한다.

알고 있었지만, 문제풀이시에는 떠올리지 못했다.

counting sort를 사용한 두번째 풀이의 경우 입력값을 받을 때, 서류 심사 순위를 인덱스로 받고, 면접 순위를 인덱스에 대응대는 값으로 입력했다. 

 

문제에서 고려할 점은, 합격할 지원자는 다른 지원자보다 적어도 한가지 이상의 순위에서 앞서야한다는 점이다.  

그래서 둘중 서류 심사 순위에 대하여 오름차순으로 정렬한뒤 1등한 사람의 면접 순위보다 우수한 지원자를 2등부터 탐색하며, 면접순위를 업데이트 했다. 

 

1. 내장함수 사용

import sys
input=sys.stdin.readline

T=int(input())

def function(): #sort로 정렬.
    N=int(input())
    lst=[list(map(int,input().split())) for _ in range(N)]
    lst.sort()
    answer=[lst[0]]
    save=lst[0][1]
    for i in range(1,N):
        if save>=lst[i][1]:
            answer.append(lst[i])
            save=lst[i][1]
    print(len(answer))


for i in range(T):
    function()

 

2. Counting sort 사용

import sys
input=sys.stdin.readline

T=int(input())

def function():
    N=int(input())
    lst=[0]*(N+1)
    for i in range(N):
        score1, score2 = map(int, input().split())
        lst[score1]=score2
    cnt=1
    save=lst[1]
    for i in range(2,N+1):
        if save>=lst[i]:
            save=lst[i]
            cnt+=1
    print(cnt)

    

for i in range(T):
    function()