문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/152995
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이 문제의 핵심은 인센티브를 받을 수 있는 직원들에 한해서만 석차를 구하는 것이었습니다.
알고리즘은 아래와 같습니다.
1. 반복문을 통해 완호가 인센티브를 받을 수 있는지 확인하고 인센티브를 받을 수 없다면 -1을 반환하면서 프로그램을 종료합니다.
2. 완호가 인센티브를 받을 수 있다면 인센티브를 받을 수 있는 직원들만 남겨야 하는데 해당 과정을 무턱대고 O(N^2)으로 처리할 경우 scores의 길이가 최대 10만이기 때문에 TLE가 발생할 수 있습니다.
2.1 따라서, 우선 근무태도 점수 내림차순으로 정렬한 후 i번째 직원은 [0, i)까지만 비교하는 방식으로 인센티브를 받을 수 있는 직원들의 점수 합을 map에 기록합니다. (sum2cnt는 점수 합의 동석차수를 의미합니다.)
2.2 위 과정을 진행하면서 나올 수 있는 점수 합의 종류를 scoreList 벡터에 추가해 줍니다.
3. scoreList 벡터를 정렬한 뒤 가장 높은 점수 합부터 완호가 받은 점수합까지 순회하며 완호의 석차를 구해주고 반환해 줍니다.
개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
'알고리즘 > programmers' 카테고리의 다른 글
| [Programmers] 진료과별 총 예약 횟수 출력하기 (0) | 2023.01.25 |
|---|---|
| [Programmers] 과일로 만든 아이스크림 고르기 (0) | 2023.01.24 |
| [Programmers] 시소 짝궁 (4) | 2023.01.20 |
| [Programmers] 성분으로 구분한 아이스크림 총 주문량 (0) | 2023.01.18 |
| [Programmers] 평균 일일 대여 요금 구하기 (0) | 2023.01.17 |