[ BOJ 1946 ] 신입 사원(Python)

uoayop·2021년 6월 7일
0

알고리즘 문제

목록 보기
92/103
post-thumbnail

문제

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

A의 성적이 B의 성적에 비해 (서류 성적, 면접 성적) 모두 떨어진다면, A는 탈락이다.


문제 풀이

틀린 문제 풀이

다른 지원자와 비교했을 때 서류, 면접 성적 둘 중 하나라도 높으면 탈락시키지 않는다.

처음 배열을 정렬할 때 sorted를 두번 써서, 서류와 면접 점수가 섞이는 실수를 했다. ..🙂

humans = sorted([sorted(list(map(int,input().rsplit()))) for _ in range(n)])


정렬한 배열의 첫번째 요소는 (서류 점수,면접 점수) 가 가장 높은 사람이다.

그 사람보다 서류와 면접 점수 모두 낮은 지원자가 있다면 카운트 해준 뒤, 전체 지원자 수에서 빼줬다.

c1, c2 = humans[0]
cnt = 0
for i in range(1,n):
    t1, t2 = humans[i]
    if c1 < t1 and c2 < t2:
        cnt += 1

print(n-cnt)

🔥 서류 점수나 면접 점수가 높은 경우는 탈락되지 않기 때문에 이 코드는 틀렸다!!!

올바른 문제 풀이

humans = sorted([list(map(int,input().rsplit())) for _ in range(n)])

서류 점수만 기준으로 정렬해주었다.

compare = humans[0][1]

면접 점수만 비교해줄 것이다.

cnt = 0

for i in range(1,n):
    target = humans[i][1]
    compare = min(compare, target)
    if compare < target:
        cnt += 1

배열엔 서류 점수를 기준으로 오름차순으로 정렬 되어있다.

즉, 뒤에 위치한 요소는 앞에 있는 요소보다 서류 점수가 낮다는 뜻이다.

따라서 앞에 위치한 요소와 비교했을 때 면접 점수도 낮으면 탈락한다는 것을 의미한다.
if compare < target: cnt += 1

비교를 하면서 더 낮은 면접 점수가 있으면, 갱신해준다.
compare = min(compare, target)


코드

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    humans = sorted([list(map(int,input().rsplit())) for _ in range(n)])

    print(humans)

    compare = humans[0][1]
    cnt = 0
    for i in range(1,n):
        target = humans[i][1]
        compare = min(compare, target)
        if compare < target:
            cnt += 1
    
    print(n-cnt)
profile
slow and steady wins the race 🐢

0개의 댓글