[Python] 그리디- 1946. 신입사원

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

1946번: 신입 사원

>> 문제 포인트

이 문제가 헷갈리는 이유는 기준점이 두개이기 때문이다.

즉, 서류심사의 랭킹과 면점심사의 랭킹을 동시에 고려해주어야 하기 때문에 문제 풀이에 막힘이 있었다.

 

따라서, 정렬을 통해 2가지 기준점을 한가지로 줄일 필요가 있다.

 

예를 들어

 

서류|면접

1 | 4

3 | 2

4 | 1

5 | 5

2 | 3

 

이렇게 정리되어 있는 표의 경우 두가지 기준에 조건을 고려해야 하지만

 

이것을 서류 랭킹순으로 나열하게 되면 

 

서류|면접        서류|면접

1 | 4           =>   1 | 4

3 | 2                  2 | 3

4 | 1                  3 | 2

5 | 5                  4 | 1

2 | 3                  5 | 5

 

이미 서류는 1등부터 나열이 되어 있기 때문에

던져야 하는 질문은 한가지로 축소된다.

=> 면접 랭킹이 기존 채용 인원의 최고 랭킹보다 높은가?

 

따라서 서류면접 1등의 면접 랭킹이 4라면

다음부터 최고랭킹을 갱신하며 인원을 세자

 

result=1(서류 1등은 무조건 채용되므로)

 

[대소관계 비교시 랭킹이라는 점에 주의]

 

서류면접 순위 순으로 현재 면접 최고랭킹을 비교

=> 서류 1등 면접랭킹= 현재 최고랭킹(4) < 서류 2등 면접랭킹(3)     -> result+=1 / top=3

=> 현재 최고랭킹(3) < 서류3등 면접랭킹(2)                                       -> result+=1 / top=2

=> 현재 최고랭킹(2) <  서류4등 면접랭킹(1)                                     -> result+=1 / top=1

=> 현재 최고랭킹(1) > 서류 5등 면접랭킹(5)                                     => 아무처리도 안함.

 

result=4

---

 

>>풀이 코드

 

n= int(input())

for _ in range(n):

    k= int(input())

    data=[]

    for _ in range(k):

      a,b= map(int, input().split())

      data.append([a,b])

    #서류심사 랭킹을 더해서 정렬

    data.sort()

    #서류 1등 면접 랭킹이 시작 최고랭킹

    top= data[0][1]

    #서류 1등은 무조건 채용되므로

    result=1

    #서류 면접 순으로 면접 랭킹을 비교

    # 최고랭킹(top)보다 높으면 갱신 + (result+1)

    for i in data[1:]:

      if i[1]<top:

        result+=1

        top=i[1]

    print(result)