문제 설명 및 제한사항
문제 설명
완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다.
각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.
제한 사항
•
1 ≤ scores의 길이 ≤ 100,000
•
scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.
◦
scores[0]은 완호의 점수입니다.
◦
0 ≤ a, b ≤ 100,000
•
완호가 인센티브를 받지 못하는 경우 -1을 return 합니다.
아이디어 및 해결 방법
쉬워 보이는데 이상하게 잘 안 풀리는 문제였습니다.
우선 완호의 두 점수 (target_a, target_b), 그리고 점수 합 (target_score)를 저장해 두고 사원의 점수들을 첫번째 점수의 내림차순, 첫 번째 점수가 같다면 두 번째 점수의 오름차순으로 정렬해 둡니다. 이 리스트를 scores라 합시다.
당연히 두 번째 점수만 보면 정렬된 상태가 아니겠지요! 하지만 중요한 성질은, scores 리스트에서 뒤에 나온 학생의 첫 번째 점수(a)는 항상 앞에 나온 학생의 첫 번째 점수보다 같거나 작다는 겁니다. 그러면 문제가 간단해지는 것이, 나중에 탐색하는 학생의 두 번째 점수(b)가 먼저 탐색하는 학생의 두 번째 점수보다 작은 경우가 단 하나라도 있으면 해당 학생보다 두 점수가 높은 학생이 있음이 보장되게 됩니다. 천천히 생각해보면 좋습니다.
직전 학생과 a가 같은 경우도 있으니까, 꼭 b가 작다고 a와 b 둘다 작다고 말할 수 없는 것 아니냐구요?
아닙니다. 정렬 상태가, 두 번째 점수에 대해서 오름차순이므로, a가 같은 두 학생은 먼저 나온 학생이 항상 더 큰 b 값을 갖게 되어서 그런 경우는 없습니다!
정리하면, 뒤에 나온 학생의 두 번째 점수가 앞에 나온 어떤 학생의 (maxb) 보다 크거나 같을 때만 해당 학생은 인센티브 후보가 될 수 있게 됩니다. 이를 반영해서 순위를 원호의 순위를 잘 계산해주면 됩니다.
코드
def solution(scores):
answer = 0
target_a, target_b = scores[0]
target_score = target_a + target_b
# 첫번째 점수에 대해서 내림차순,
# 첫 번째 점수가 같으면 두 번째 점수에 대해서 오름차순으로 정렬합니다.
scores.sort(key=lambda x: (-x[0], x[1]))
maxb = 0
for a, b in scores:
if target_a < a and target_b < b:
return -1
if b >= maxb:
maxb = b
if a + b > target_score:
answer += 1
return answer + 1
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges