[프로그래머스] 인사고과 - C++

문제 설명

완호네 회사는 연말마다 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 합니다.

---

입출력 예scoresresult

[[2,2],[1,4],[3,2],[3,2],[2,1]]

4

---

입출력 예 설명

5 번째 사원은 3 번째 또는 4 번째 사원보다 근무 태도 점수와 동료 평가 점수가 모두 낮기 때문에 인센티브를 받을 수 없습니다. 2 번째 사원, 3 번째 사원, 4 번째 사원은 두 점수의 합이 5 점으로 최고점이므로 1 등입니다. 1 등이 세 명이므로 2 등과 3 등은 없고 1 번째 사원인 완호는 두 점수의 합이 4 점으로 4 등입니다.

---

N이 10만이므로 O(N^2)으로 해결하는 문제가 아니다. 따라서 정렬을 한 다음 linear 하게 탐색을 하는 방법을 생각할 수 있다.

a를 기준으로 내림 차순 정렬을 한 다음 a 가 같은 경우 b를 오름 차순으로 정렬한다.

그렇게 되면 a가 같은 그룹에서 제일 마지막에 있는 수의 b 가 제일 크므로 b를 pivot으로 설정하여 하위 그룹에서 인센티브를 받을 수 없는 사람들을 거를 수 있다. 하위 그룹에서 b가 pivot과 같아지는 시점부터는 인센티브를 받을 수 있는 리스트에 추가한다.

 

---

정렬을 하고 linear 하게 확인하는 방법까지는 생각했지만 더 이상 생각이 나지 않아 구글링을 하여 아이디어를 얻었다. 아이디어를 이해하는데도 조금 시간이 걸렸다. 그래도 a 내림차순 b 오름 차순 정렬의 아이디어를 활용하여 그 이후의 코드를 작성했지만 일부 테케를 통과할 수 없었다. 다시 보니 완호가 인센티브에서 제거되는 경우를 생각하지 못해서 추가하였지만 아직도 안 되는 것들이 있었다. 다시 자세히 살펴보니 cmp 함수에서 first가 같은 경우에 return 이 없었던 것이었다. return을 추가하니 잘 돌아갔다. 요즘 들어 이렇게 한 끝 차이로 못 푸는 경우가 많은 것 같다. 코드 에디터를 쓸 때는 잘 못 쓴 구문의 경우 에러를 바로 띄워줬지만 프로그래머스는 뜨지 않아 시간이 더 걸리는 것 같다. 프로그래머스에 익숙해져야겠다!