백준 1946: 신입 사원 (Python)

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

1946번: 신입 사원

 

처음 푼 코드 - 시간 초과

import sys
t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())
    list1 = [0 for i in range(n)]
    list2 = [0 for i in range(n)]

    for j in range(n):
        r1, r2 = map(int, sys.stdin.readline().split())
        list1[r1 - 1] = j + 1
        list2[r2 - 1] = j + 1

    k = n
    cnt = 0

    for j in list1:
        if list2.index(j) < k:
            cnt += 1
            k = list2.index(j)

    print(cnt)

 

리스트 두개를 만들어서 비교하는게 비효율적이었던 것 같다

그래서 리스트 하나로 합쳐서 다시 풀었다

 

import sys
t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())
    p = []

    for j in range(n):
        r1, r2 = map(int, sys.stdin.readline().split())
        p.append([r1, r2])

    p.sort()
    k = n + 1
    cnt = 0

    for j in range(n):
        if p[j][1] < k:
            cnt += 1
            k = p[j][1]

    print(cnt)

 

푼 방식은 똑같음

 

 

생각보다 시간이 좀 걸린 문제였다

 

슬퍼요💧

 

멍청하게 중간에 print로 확인 코드 넣었다가 안 지우고 그냥 제출해서 틀림~