BOJ1946 신입 사원

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

1946번: 신입 사원

 

난이도: 실버1

소요시간: 40분

 

rank리스트(input)를 1차적으로 오름차순으로 정렬을 해준다. 그 후 서류순위 1위를 result리스트에 넣는다. 

rank리스트를 순환하면서 result리스트에 마지막에 들어간 사람과 면접순위를 비교한다. 만약 순위가 높다면 result리스트에 추가한다.

이전의 사람과만 비교를 하면 자동적으로 이전전의 사람들도 자동으로 체킹이 된다. 

 

문제를 제출하면서 의문이 하나 들었는데 문제에 최대합격자수를 구하라고 하였다. 지금 이대로 구한 방법이면 서류1위는 무조건 합격인데 서류1위를 탈락시키는 경우에 더 많은 합격자가 나올 경우는 없을까 라는 생각이 들었다. 그런데 제출시 정답이라고 판정이 났고 나는 다른 사람들의 코드를 찾아보았다. 다른 사람들도 나랑 같은 방법으로 문제를 풀었다. 이 풀이에는 문제가 없을까..?

-> 생각을 해보니 그럴 경우는 없다. 왜냐하면 서류1순위를 빼고 서류2순위를 무조건 합격으로 시키면 합격자수는 +-0이고 뒤에 result에 추가되는 것들도 변하지 않는다. 

서류2순위의 면접순위가 서류1순위보다 크다면 서류2순위는 합격자가 될 수 없기에 답이 될 수 없다.

또한 서류2순위의 면접순위가 서류1순위보다 작으면 다음에 추가되는 값은 결국 같더나 작기 때문에 답이 될 수없다.

#9:20 실버1

import sys
T= int(sys.stdin.readline())

def solve():
    rankList=[]

    N=int(sys.stdin.readline())
    for i in range(N):
        rank1,rank2=map(int,sys.stdin.readline().split())
        rankList.append([rank1,rank2,i])
    rankList.sort(key=lambda x: x[0] )
    # print(rankList)

    resultList = []
    resultList.append(rankList[0])
    for i in range(1,N):
        if rankList[i][1]<resultList[-1][1]:
            resultList.append(rankList[i])

    # print(resultList)
    return (len(resultList))


###그냥 예쁘게 출력하려고 아래처럼 한거임
ans=[]
for _ in range(T):
    ans.append(solve())

for a in ans:
    print(a)