파이썬 알고리즘 307번 | [백준 1946번] - 신입사원, 그리디

307. 신입사원, 그리디

1) 어떤 전략(알고리즘)으로 해결?

그리디

2) 코딩 설명

• 두 순위 중 하나는 높아야 하는데, 일단 서류 순위로 정렬 시켜두고 서류 순으로 뽑으면, 이전에 뽑혀서 팀에 합류한 이들의 면접 순위보다 높으면 팀에 합류가 가능합니다.
• 결국 그리디 문제라고 판단했고 정렬 및 가장 높은 서류 순으로 뽑는 과정에서 최대/최소값 추출에 가장 적합한 heap을 사용했습니다.

<내 풀이>

# https://www.acmicpc.net/problem/1946
import sys
import heapq

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

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

    for j in range(n) : 
        s,m = map(int ,sys.stdin.readline().rstrip().split()) # 서류 순위 / 면접 순위
        heapq.heappush(hq,(s,m))
        # 서류 순위가 가장 높은 것부터 
    
    min_s, min_m = heapq.heappop(hq)    
    before_rank = min_m
    answer = 1 # 서류 1위인 사람 먼저 count 
    while hq :
        now_s, now_m_rank = heapq.heappop(hq)
        if now_m_rank < before_rank : 
            answer+=1
            before_rank = now_m_rank

    print(answer)

< 내 틀렸던 풀이, 문제점>

• 틀렸던 부분은 팀에 합류한 이들의 면접 순위를 기준으로 비교했어야 하는데 매번 갱신을 한 것이 오답의 원인이었습니다.

# https://www.acmicpc.net/problem/1946
import sys
import heapq

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

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

    for j in range(n) : 
        s,m = map(int ,sys.stdin.readline().rstrip().split()) # 서류 성적 / 면접 순위
        heapq.heappush(hq,(s,m))
        # 서류 점수가 가장 큰 것부터 
    
    min_s, min_m = heapq.heappop(hq)    
    before_rank = min_m
    answer = 1 # 서류 1위인 사람 먼저 count 
    for _ in range(n-1) :
        now_s, now_m = heapq.heappop(hq)
        if now_m < before_rank : 
            answer+=1
        before_rank = now_m 
        # 매번 갱신하는 이 부분에서 오답 , 팀에 합류되는 멤버들이 생길 때만 갱신해야 합니다.

    print(answer)