[백준] 1946 신입사원 (파이썬 Python)

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

1946번: 신입 사원

문제 설명

 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

---

풀이 과정

• 나의 풀이

① 이 문제에서 직관적으로 파악된 것은 '주어진 지원자들 중에서 다른 모든 지원자와 비교하였을 때 서류심사 성적과 면접 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발되는구나...'이다.

② 아이디어 열기

  서류심사 성적과 면접 성적 모두 등수를 표기한다. 

(1) 예제 분석하기

  일단 예제를 살펴보자. 

  지원자의 수가 5명이고 지원자들의 성적은 다음과 같다.

 지원자1 : (서류심사 성적 : 3등 , 면접심사 성적 : 2등)  

 지원자2 : (서류심사 성적 : 1등 , 면접심사 성적 : 4등)

 지원자3 : (서류심사 성적 : 4등 , 면접심사 성적 : 1등)

 지원자4 : (서류심사 성적 : 2등 , 면접심사 성적 : 3등)

 지원자5 : (서류심사 성적 : 5등 , 면접심사 성적 : 5등)

  이와 같은 상황일 때 신입 사원으로 채용될 수 있는 멤버는 지원자1,지원자2,지원자3,지원자4이므로 합격인원은 4명이다.

  '신입 사원으로 채용될 수 있는 멤버가 누구일까...?'를 생각하며 구하는 과정에서  기준을 서류심사 성적 1등부터 2등,3등,4등,5등 순서로 고려하였다. 그 이유는 일단 무조건 뽑히는 사람은 두 성적 중 어떤 성적이든 1등한 사람이다. 그 뒤로 만약 서류심사 성적 2등이 서류심사 성적 1등보다 면접심사 성적이 좋으면 뽑히게 되고, 서류심사 성적 3등이 서류심사 성적 1,2등보다 면접심사 성적이 좋으면 뽑히게 되기 때문이다.

 

(2) 코드 구현 (첫번째 시도)

  내가 직접 구한 방법을 코드로 구현하면 다음과 같다.

# 1946 신입사원
import sys
input = sys.stdin.readline
T = int(input())

for i in range(T) :
    n = int(input())
    people_lst = [0]*n
    for j in range(n) :
            t1 ,t2 = map(int,input().split())
            people_lst[j] = [t1,t2]

    people_lst_sorted_0 = sorted(people_lst, key = lambda x : x[0])
    hired = 1
    for j in range(1,n) :
        num = 0
        for k in range(j) :
            if people_lst_sorted_0[j][1] < people_lst_sorted_0[k][1] :
                num += 1
            if num == j :
                hired += 1

    print(hired)

  첫번째 for문으로 성적을 people_lst에 저정하고, peopl_lst_sorted_0 리스트를 통해 서류심사 성적 순으로 리스트를 정렬한 뒤 이중 for문을 통해 hired되는 사람을 구했다.

  하지만 결과는.....!!

  시간 초과로 인한 오답처리다.. ㅠㅠㅠㅠ

 

(3) 코드 구현(두번째 시도)

  왜 시간초과가 걸렸는지 내 코드를 뜯어본 결과 이중for문으로 인해 시간복잡도가 증가했기 때문인 거같았다.

  이를 해결하기 위해 오직 하나의 for문을 통해 해결해야했고 그 코드는 다음과 같다.

# 1946 신입사원
import sys
input = sys.stdin.readline
T = int(input())

for i in range(T) :
    n = int(input())
    people_lst = [0]*n
    for j in range(n) :
            t1 ,t2 = map(int,input().split())
            people_lst[j] = [t1,t2]

    people_lst_sorted_0 = sorted(people_lst, key = lambda x : x[0])
    hired = 1
    man = people_lst_sorted_0[0][1]
    for j in range(1,n) :
        if people_lst_sorted_0[j][1] < man :
            man = people_lst_sorted_0[j][1]
            hired += 1

    print(hired)

 

① 서류심사 성적으로 정렬한 리스트의 핵심은 '면접 성적' 비교를 통해 채용 여부를 결정하는 것이다. 왜냐하면 서류심사 성적을 이미 정렬하였으니깐 서류심사를 통해 채용될 희망은 이미 사라졌다...!!

② 예제 1의 상황을 다시 살펴보자. 

지원자의 수가 5명이고 지원자들의 성적은 다음과 같다.

 지원자1 : (서류심사 성적 : 3등 , 면접심사 성적 : 2등)  

 지원자2 : (서류심사 성적 : 1등 , 면접심사 성적 : 4등)

 지원자3 : (서류심사 성적 : 4등 , 면접심사 성적 : 1등)

 지원자4 : (서류심사 성적 : 2등 , 면접심사 성적 : 3등)

 지원자5 : (서류심사 성적 : 5등 , 면접심사 성적 : 5등)

 위의 상황을 서류심사 성적으로 정렬하면 다음과 같다.

 지원자2 : (서류심사 성적 : 1등 , 면접심사 성적 : 4등)  

 지원자4 : (서류심사 성적 : 2등 , 면접심사 성적 : 3등)

 지원자1 : (서류심사 성적 : 3등 , 면접심사 성적 : 2등)

 지원자3 : (서류심사 성적 : 4등 , 면접심사 성적 : 1등)

 지원자5 : (서류심사 성적 : 5등 , 면접심사 성적 : 5등)

 지원자4는 지원자2보다 면접심사 성적이 낫고, 지원자 1은 지원자 4,2의 면접심사 성적보다 나으므로 지원자4,지원자1 모두 채용되었다. 이 과정에서 눈 여겨볼 것은 비교 과정에서 사실상 지원자 1이 지원자2와 면접심사 성저을 비교할 필요 없이 지원자 4보다 면접심사 성저이 높으면 사실상 채용된다.

 그렇기에 변수 man의 값을 채용될 때마다 갱신해주었다.

 결과는...!!

 

 성공-!-!-!

---

후기

 오랜만에 정렬문제를 푸는 듯했다. 문제 푼 후 카테고리를 보니 그리디 알고리즘이라는데... 말로만 듣던 그리디 알고리즘?!?!?! 이라는 생각에 흠칫하였다.