[백준] 1946번 | 신입 사원

풀기 전 생각 정리

1) 두가지 면접의 순위가 낮을수록 좋기 때문에, list에 [전자 순위, 후자 순위]로 넣어 비교하자.
2) list에 넣은 값들을 '전자 순위' 기준으로 sort해서 진행한다.
3) 복잡도를 생각해야 하기 때문에 앞서 전자 순위들의 '후자 순위'값의 min값을 기억해 앞으로 비교할 사원들과 순위를 비교한다.

정리 : 사원들을 모든 사원들과 비교할 수 없으니, sort로 전자 순위 순서를 정해주고 후자 순위의 min값을 저장해 비교한다.

코드

import sys

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    arr = []
    for j in range(n):
        arr.append(list(map(int, sys.stdin.readline().split())))
    arr.sort(key=lambda x:(x[0],x[1]))

    result = 0
    value = int(1e9)
    for p in range(n):
        if arr[p][1] < value:
            result += 1
            value = arr[p][1]
    print(result)

최적 코드를 참고해서 짠 코드

import sys

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    arr = [0] * (n+1)
    for j in range(n):
        x, y = map(int, sys.stdin.readline().split())
        arr[x] = y

    arr[0] = 1
    value = arr[1]
    for p in range(2, n+1):
        if arr[p] < value:
            arr[0] += 1
            value = arr[p]
    print(arr[0])

리뷰

복잡도를 처음부터 생각하고 접근했기에 쉽게 해결한 문제였다. 하지만 제출한 사람들의 최적 코드를 보고 뒤통수를 맞았다. 내 코드가 최적 코드의 시간에 7배가 걸렸던 것.
두 코드의 차이점은 sort를 하지 않았다는 점이다. 동일한 순위가 나오지 않는다는 점을 이용해 일차원 list로 순위를 매겨놓았다. arr[전자 순위] = 후자 순위라는 식으로 말이다.

결론 : 두가지 변수가 나온다고 무작정 이차원 리스트를 이용하려 하지 말자,, 일차원 list로도 순서를 나타낼 수 있다.