1946 신입사원

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

1946번: 신입 사원

 

내 풀이(일주일째 못풀다가 힌트보고 겨우 맞춤)

import sys

m = int(input())
sum = []
for i in range(m):
    n = int(input())
    ary = []
    for j in range(n):
        x = sys.stdin.readline().split()
        ary.append([])
        ary[j].append(int(x[0]))
        ary[j].append(int(x[1]))
    ary.sort()
    count = 1
    min = ary[0][1]
    for k in range(1, n):
        if min > ary[k][1]:
            min = ary[k][1]
            count += 1
    sum.append(count)
for i in sum:
    print(i)

sys.stdin.realine()는 input()보다 시간이 단축된다. 그리고 import sys를 써줘야 사용가능하다. 

이 문제는 for문을 1개 줄이니까 겨우 풀었다. 우선 앞에 등수를 정렬하고 1등의 다른 점수의 등수를 min에 넣었다. 그리고 정렬한 등수대로 비교하면서 만약에 밑에 있는 등수가 더 높다면(즉, 숫자가 작다면) min을 밑에꺼의 등수로 바꿔주고 다시 비교한다. 그리고 위에꺼의 등수보다 낮다면 그 사람은 탈락하게된다.