문제
언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
출력
각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.
예제 입력 1
2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1예제 출력 1
4
3일단 이 문제같은 경우 왜 4개, 3개가 나오는지 부터 살짝 헤깔렸다.
그래서 분석해서보니, 두 수 중 하나라도 나머지 숫자들보다는 무조건 크면 합격인 것이여서 처음엔 서류에 대해 다 체크하고 본인보다 높은 순위를 가진 사람, 그 사람은 서류 순위, 면접 순위를 튜플 ()로 가지고 있다.
그래서 서류가 나머지 수랑 비교해서 작으면 담고, 면접도 그런식으로 담을 생각을 했으나, 조건이 너무 애매했다.
그래서 문제풀이를 맨 처음엔
# 1차 서류 심사 + 2차 면접 시험
# 적어도 하나는 다른 지원자보다 떨어지지 않는 자만 선발
# 즉 1차 2차 둘 다 최소 값 이상이여야만 함
# 최소값 도출해서 그것보다 큰 애들 뽑아내기
# 최소값보단 다 커야되고, 한명 한명과 비교했을때의 성적에 대해 모두 떨어지면 선발X (2가지 조건임)
# 오케이 성적의 순위인것임 입력 값은
# 서류 성적 비교해서 다른 인원보다 더 낮은 수면 set에 담기
# 2차 면접 성적 비교해서 다른 인원보다 더 낮은 수면 set에 담기
# 그렇게 넣은 set의 length가 N-1개와 같으면 + 1
# import sys
# input = sys.stdin.read
# data = input().split()
# index = 0
# T = int(data[index])
# index += 1
# for _ in range(T):
# case = []
# N = int(data[index])
# index += 1
# for _ in range(N):
# document_ranking, interview_ranking = int(data[index]), int(data[index+1])
# case.append((document_ranking, interview_ranking))
# index += 2
# for i in range(N-1):
# result_case = set()
# if case[i][0] < case[i+1][0]:
# result_case.add(case[i])
# elif case[i][1] < case[i+1][1]:
# result_case.add(case[i])
# print(result_case)
# ========================================
# 위의 접근 법은 set이 들어온 값을 정렬할 때 랜덤으로 정렬하기 때문에 성립하지 못함 case의 [i]번째 값이 뭔지 알 수 없음일단 본인이 나머지 수랑 비교해서 한명보다 낮은 순간 무조건 새로운 case안에 담아지는 것 자체가 문제였다. 그런식이면 순위가 1이면 모든 수가 담기기에...
그래서 푼 두번째 코드는
# 일단 index 값들을 sort로 오름차순 정렬
# 1 4
# 2 3
# 3 2
# 4 1
# 5 5
# 그 후에 index 1의 값을 비교
# 4 < 무한대 + 1
# 최소값 = 4
# 3 < 최소값 + 1
# 최소 값 = 3(2 수를 비교한 최소 값임)
# 2 < 최소값 + 1
# 최소 값 = 2(3 수 중 가장 최소값)
# 1 < 최소값 +1
# 최소 값 = 1(4수중 가장 최소값)
# 5 > 최소값
# 그래서 총 +4가됨위의 설명대로 서류 순위를 sort로 오름차순 정렬 후에? 면접 순위가 최초(무한대)보다 작으면 +1, 그리고 최소값은 그 면접 순위 넣기.
이런식으로 첫번째부터 비교해서 올라가면 예를들어 세번째 숫자가 앞에 2개의 최소값보다 작으면?? 뒤에 4번째 5번째는 볼 필요없이(왜냐면 이미 서류가 순위가 앞서고 있기 때문에) 앞에껄로 비교를 해서 counting 할 수 있는 코드가 되는 것이였다.
그동안은 뒤에껄로만 비교했던 로직을 짯는데, sort로 정리하고 나니 앞에껄로만 비교분석이 가능하구나 느꼈다. 왜냐면 최소값은 앞의 값들의 최소값이므로, 그 수보단 작아야 +1 즉, 하나라도 순위가 높다는 의미이기에...
최종 코드
import sys
input = sys.stdin.read
data = input().split()
# 0 인덱스부터 늘려줄 예정
index = 0
# 전체 테스트 케이스 개수
T = int(data[0])
# 그 다음 인덱스 값
index += 1
# T만큼 반복
for _ in range(T):
#테스트의 개수
N = int(data[index])
index += 1
#테스트 결과 담을 리스트
test = []
# N만큼 반복
for _ in range(N):
# 한번에 서류, 면접 랭킹 담아줄 예정
document_ranking, interview_ranking = int(data[index]), int(data[index+1])
test.append((document_ranking, interview_ranking))
# +2씩 처리해야 다음 줄 확인됨
index += 2
# 일단 서류에 대해 랭킹 순으로 정렬
test.sort()
# 면접 성적 최소 값(어떠한 값을 넣어도 무한대보단 작게 됨)
min_interview_rank = float('inf')
# 총 통과한 인원 수
exam_pass_count = 0
for _, interview_rank in test:
if interview_rank < min_interview_rank:
exam_pass_count += 1
min_interview_rank = interview_rank
print(exam_pass_count)나머지 하나하나 분석하기엔 이젠 익숙하고,
float('inf')
무제한 양의 값
이 부분만 체크하면 될 것 같다
그리고
for _, interview_rank in test:
if interview_rank < min_interview_rank:
exam_pass_count += 1
min_interview_rank = interview_rank이 부분이 머리로는 이해되지만 실제로 코드 구현을 이렇게 해본적은 없어서 참신했던 경험이였다.
