반응형
문제풀이
1. 각 요소가 (서류 순위, 면접 순위)인 리스트 l을 만든 후, 서류 순위를 기준으로 l을 정렬해줍니다.
2. 정렬된 l에서 앞에서부터 튜플을 하나씩 꺼내며 면접 순위가 이전에 선발된 사람보다 높은(숫자가 낮은) 사람을 선발하게 됩니다.
백준의 두번째 예시
[(1, 4), (2, 5), (3, 6), (4, 2), (5, 7), (6, 1), (7, 3)]
를 살펴보면 다음과 같습니다.
- 먼저 서류 1등은 당연히 뽑히게 됩니다. 2, 3등은 서류 순위, 면접 순위 모두 서류 1등보다 낮으므로 선발되지 않습니다.
- 서류 4등의 경우, 서류 1등보다 면접 등수가 높으므로 선발됩니다.
- 서류 5등의 경우에는 서류 4등보다 면접 등수도 낮으므로 선발되지 않습니다.
- 서류 6등의 경우에는 서류 4등보다 면접 등수가 높으므로 선발됩니다.
- 서류 7등의 경우에는 면접 등수도 서류 6등보다 낮으므로 선발되지 않습니다.
Python Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import sys
readline = sys.stdin.readline
def main(n):
for _ in range(n):
#l = sorted([tuple(map(int,readline().split())) for _ in range(int(readline()))],key = lambda x : x[0])
l = []
for x in range(int(readline())):
l.append(tuple(map(int,readline().split())))
l = sorted(l,key = lambda x : x[0])
tmp = l[0][1]
ans = 1
for n,m in l:
if m < tmp :
tmp = m
ans += 1
print(ans)
if __name__ == '__main__':
n =int(readline())
main(n)
|
cs |
Line 7 : l은 (서류 등수, 면접 등수)가 들어갈 리스트입니다. Line 7~10을 Line 6 한줄로 축약할 수 있습니다.
*축약할 경우 소요시간이 3584 -> 3996 ms로 길어지게됩니다.
문제 링크
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성
www.acmicpc.net
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 4673 셀프 넘버 Python (0) | 2020.12.10 |
|---|---|
| 백준 4344 평균은 넘겠지 Python (0) | 2020.12.09 |
| 백준 20162 간식 파티 Python (0) | 2020.12.08 |
| 백준 1149 RGB거리 Python (0) | 2020.12.08 |
| 백준 1309 동물원 (0) | 2020.12.07 |