[백준 1946] 신입 사원

 

▶ 코드

 

# 문제     : 서류,면접 등수가 모두 자기보다 낮은게 있으면 OUT

# 아이디어 : 1 .서류등수 기준으로 오름차순 한 다음,
#            2. 서류등수 1등인사람의 면접점수를 min값으로 두고,
#            3. 서류등수가 올라가는 순서로 되어있으므로, 그 다음번 원소의 면접등수는 앞에꺼보다 무조건 높은등수여야만 한다.
#            4. (따라서 min값을 계속 갱신해 나가야 한다)


T = int(input())

for _ in range(T):
    
    n = int(input())
    s = [0]*(n+1)
    
    # 입력
    for i in range(n):
        a, b = map(int, input().split())
        s[a] = b
    #print(s)

    min_number = s[1]           # 서류등수 1등인 사람의 면접등수 

    c = 0
    for i in range(2, len(s)):  # 서류점수 2등~ n등까지 차례대로 면접등수 검사 
        if s[i] > min_number:
            #print('걸러진것->(', i, s[i], ')')
            c += 1
        else:
            min_number = s[i]
    print(n - c)
    

# 정답 : https://pacific-ocean.tistory.com/343



'''시간초과'''
'''
#t=[[3,2],[1,4],[4,1],[2,3],[5,5]]
#t=[[3,6],[7,3],[4,2],[1,4],[5,7],[2,5],[6,1]],
# 배열에서 둘다 높아지는 경우 OUT

T = int(input())

for _ in range(T):
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split())))
        
    t1 = sorted(t, key=lambda x: x[0])
    t2 = sorted(t1, key=lambda x: x[1])
    #print(t2)

    c = 0
    i = 0
    j = 1
    length = len(t2)

    while j < len(t2):
        if t2[i][0] > t2[j][0] or t2[i][1] > t2[j][1]:
            i += 1
            j += 1
        else:
            #print('삭제할것->', t2[j])
            t2 = t2[:j] + t2[j+1:]
            #print('t2다시 ->', t2)
            c += 1
                
    print(length-c)
'''