[백준] 1946번 : 신입 사원 (파이썬)
문제
나의 첫번째 답안
t=int(input())
for i in range(t):
n=int(input())
p=[]
cnt=1
for j in range(n):
grade,rank=map(int,input().split())#성적, 면접순위
p.append([grade,rank])
p.sort()#성적으로 정렬하기
mn=p[0][1]#성적이 1등인 사람의 면접 순위를 저장
for k in range(1,n):#1등을ㅇ 제외하고
if mn>p[k][1]:#2등부터 n등까지 면접순위 비교, mn이 더 크다면
cnt+=1#인원수 증가
mn=p[k][1]#해당 값으로 mn 초기화
print(cnt)
시간 초과라는 결과가 나왔다.
반복문이 여러개이고, 입출력이 계속 일어나므로 sys.stdin.readline
로 입출력 시간을 단축해주어야 한다.
나의 최종 답안
import sys
input=sys.stdin.readline
t=int(input())
for i in range(t):
n=int(input())
p=[]
cnt=1
for j in range(n):
grade,rank=map(int,input().split())#성적, 면접순위
p.append([grade,rank])
p.sort()#성적으로 정렬하기
mn=p[0][1]#성적이 1등인 사람의 면접 순위를 저장
for k in range(1,n):#1등을 제외하고
if mn>p[k][1]:#2등부터 n등까지 면접순위 비교, mn이 더 크다면
cnt+=1#인원수 증가
mn=p[k][1]#해당 값으로 mn 초기화
print(cnt)
접근 방법
- 최댓값 구하는 방식과 비슷하게 접근할 수 있다.(그리디 문제)
- 1등은 무조건 뽑힌다. 따라서 각 분야의 1등을 기준으로 놓고 비교해주면 된다.
- 성적을 정렬 기준으로 놓고, 성적이 동일하면 면접순위가 높은 사람을 뽑는다.
Author And Source
이 문제에 관하여([백준] 1946번 : 신입 사원 (파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yj_lee/백준-1946번-신입-사원-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)