[백준] 1946번 - 신입 사원

1차

아이디어

1차, 2차 시험 모두 동석차는 없이 1위부터 N위까지 결정된다고 가정하였다.
1) 각 테스트 케이스에 대하여 1차 시험을 기준으로 오름차순 정렬한다.
2) 이때 1차 시험 1등은 무조건 합격이므로(적어도 하나가 다른 지원자보다 떨어지지 않으면 합격), 1차 시험 2등부터 2차 시험 성적을 확인한다.
3) 1차 시험 2등은 1차 시험 1등의 2차 시험 성적보다 높으면 합격이다. 1차 시험 3등은 1차 시험 1,2등의 2차 시험 성적보다 높으면 합격이다. 이러한 방식으로 모든 지원자의 성적을 체크하면 선발 가능한 최대 인원수를 구할 수 있다.

코드

T = int(input())
test = []

for i in range(0,T):
    tmp = []
    N = int(input())
    for j in range(0,N):
        first, second = map(int,input().split())
        tmp.append((first,second))
    test.append(tmp)

for i in range(0,T):
    cnt = 1 # 1차 시험 1등은 무조건 합격
    tmp = test[i]
    tmp.sort(key=lambda x: x[0])
    for j in range(1,len(tmp)):
        count = 0
        val = tmp[j][1]
        for l in range(0,j):
            if val < tmp[l][1]:
                count += 1
            else:
                break
        if count == j:
            cnt += 1
    print(cnt)

시간 초과가 발생한다.

최종

아이디어

1차 시험 기준으로 오름차순 한 뒤, 2차 시험 값을 하나씩 비교해나가는 방식을 택했다.
이런 과정에서 for문의 수를 하나 줄일 수 있었고 시간초과를 해결할 수 있었다.
-> 등수가 더 높은 2차 시험 성적이 나오면 val값을 그 값으로 치환해주었다.적어도 1개의 성적이 높으면 신입 사원 채용조건에 부합하는 조건이므로 cnt값도 하나 증가시켜주었다.

코드

T = int(input())

for _ in range(T):
    tmp = []
    N = int(input())

    for _ in range(0, N):
        first, second = map(int, input().split())
        tmp.append((first, second))
    tmp.sort(key=lambda x: x[0])

    cnt = 1  # 1차 시험 1등은 무조건 합격

    val = tmp[0][1]

    for i in range(N):
        if val > tmp[i][1]:
            val = tmp[i][1]
            cnt += 1
    print(cnt)