Climbing the Leaderboard
문제
링크: Climbing the Leaderboard (Medium Level)
Alice의 랭킹을 구하는 문제입니다.
현재 scores와 Alice의 score를 input 값으로 받아 Alice의 Ranking을 return 하는 문제입니다. leaderboard는 Dense Ranking 을 사용하여, 점수가 같으면 같은 랭킹으로 판단됩니다. 주의할 점은 leaderboard의 score는 내림차순이며, alice의 score는 오름차순 입니다.
[input]
7 // score num
100 100 50 40 40 20 10 // scores array
4 // alice score num
5 25 50 120 // alice scores array
[output]
6 4 2 1
Score | 100 | 100 | 50 | 40 | 40 | 20 | 10 |
---|---|---|---|---|---|---|---|
Ranking | 1 | 1 | 2 | 3 | 3 | 4 | 5 |
Alice Score | 5 | 25 | 50 | 120 |
---|---|---|---|---|
Alice Ranking | 6 | 4 | 2 | 1 |
풀이
처음 문제를 보고 medium level 치고 쉽네 라고 얕봤는데 ‘Terminated due to timeout’ Error의 늪에 오래 빠져있다 나왔습니다(…)
- 우선 중복되는 score를 제거하기 위해(같은 점수는 랭킹이 같기 때문) HashSet 자료구조를 사용하였으며, HashSet을 다시 List로 변경 후 내림차순 정렬 하였습니다.
//중복되는 score 제거. scoreList index+1 = ranking
Set<Integer> scoreSet = new HashSet<>();
for (int i = 0; i < scores.length; i++) {
scoreSet.add(scores[i]);
}
List<Integer> scoreList = new ArrayList<>(scoreSet);
//내림차순 정렬
Collections.sort(scoreList);
Collections.reverse(scoreList);
-
leaderboard의 score는 내림차순이고 alice의 score는 오름차순이기에 비교하기 쉽게 alice socre array의 for문을 거꾸로 돌았습니다.
alice의 score가 leaderboard의 score보다 크거나 같을 경우 rank 숫자를 한개씩 증가시켰습니다. 만약 leaderboard를 다 돌아도 alice의 score가 leaderboard의 score보다 크거나 같은 경우가 없으면 마지막 랭크이므로 처음에 꼴찌로 가정하고 for문을 시작하였습니다.
여기서 point는 startIndex 입니다. 그냥 for문을 돌게 되면 몇몇 TestCase에서 'Terminated due to timeout' 이 발생하게 됩니다.
alice의 score가 점점 낮아질수록 leaderboard 앞에 순위는 굳이 판단할 필요가 없어집니다. 따라서 alice의 점수가 leaderboard보다 작을 경우 startIndex를 한칸씩 옮겨서 for문을 수행하였습니다. 이렇게 되면 수행시간이 짧아집니다.
int startIndex = 0;
for (int i = alice.length - 1; i >= 0; i--) {
int aliceScore = alice[i];
//꼴찌로 가정
result[i] = scoreList.size() + 1;
for (int j = startIndex; j < scoreList.size(); j++) {
if (scoreList.get(j) <= aliceScore) {
result[i] = j + 1;
break;
} else {
startIndex++;
}
}
}
위 풀이로 모든 테스트케이스를 패스하였습니다!
전체코드는 Github에서 확인할 수 있습니다.
(개인적인 풀이방식이며 더 좋은 방법이나 아이디어는 언제든 댓글 달아주세요~)
댓글남기기