[BAEKJOON] 1946 | 신입 사원

🔎 1946 | 시리얼 번호

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

---

💡 Solution

1. 먼저 서류 성적과 면접 성적을 모두 입력 받아 list화한다.
2. 서류 성적을 기준으로 정렬한다.
3. 본인보다 서류 성적이 좋은 사람들 중 가장 좋은 면접 성적보다 면접 성적이 좋으면 합격이다.
4. 이 때, 서류 성적이 1등인 사람은 절대 다른 지원자보다 모두 성적이 떨어질 수 없으므로 무조건 선발이다.

import sys
input = sys.stdin.readline

def find_passed_count(n) :
    count = 1
    candidates = []
    for i in range(n) :
        document_score, interview_score = map(int, input().split())
        candidates.append((document_score, interview_score))
        
    candidates.sort(key = lambda x: (x[0]))
    
    threshold = candidates[0][1]
    for i in range(1, n) :
        if threshold > candidates[i][1] :
            count += 1
            threshold = candidates[i][1]
        
            
    return count

t = int(input().rstrip())

while t :
    n = int(input().rstrip())
    print(find_passed_count(n))
    t -= 1

---

📌  Note

처음에 다음과 같이 이중 for문을 사용했더니 시간복잡도가 O(N^2)이 나와서 시간 초과가 떴다.
웬만하면 이중 for문은 사용하지 않을 것 !

 

import sys
input = sys.stdin.readline

def find_passed_count(n) :
    count = n
    candidates = []
    for i in range(n) :
        document_score, interview_score = map(int, input().split())
        candidates.append((document_score, interview_score))
        
    candidates.sort(key = lambda x: (x[0]))
    
    for i in range(n) :
        for j in range(i) :
            if candidates[i][1] > candidates[j][1] :
                count -= 1
                break
            
    return count

t = int(input().rstrip())

while t :
    n = int(input().rstrip())
    print(find_passed_count(n))
    t -= 1​