[codeground 연습문제 2] 프로그래밍 경진대회

 이 문제는 마지막 라운드의 사람들의 점수를 알려줬을 때, 최종 우승할 가능성이 있는 사람들의 수를 구하는 문제입니다. 점수는 참가자가 N명이라고 했을 때, 1등부터 차례대로 N점, (N -1) 점, (N - 2)점, ... , 1점 을 부여합니다.

 저는 우선 입력받은 사람들의 점수를 Arrays.sort() 함수를 이용해 정렬했습니다. 그 배열을 arr이라고 하겠습니다. arr[i] 아이가 1등을 하려면 arr[i + 1] ~ arr[N - 1] 사람들이 arr[i] 사람보다 낮은 점수를 받아야 합니다. 따라서 가장 이상적인 방법은 그 다음 사람부터 N -1, N - 2, ... , 1 점을 받으면 가능성이 있을거예요. 그 앞(arr[0] ~ arr[i - 1]) 은 생각안해도 되는 이유는 어차피 그 앞의 사람들이 어떤 점수를 받든 (arr[i] + N)점보다 낮을 것이기 때문입니다. 

 따라서 나보다 점수 높은 애들이 나보다 낮은 점수를 받았을 때를 새로운 배열 next 에 저장합니다. 위의 논리대로라면 

arr[0] + N, arr[1] + (N -1) , arr[2] + (N - 2), ... , arr[N - 1] + 1

  이 값들이 next 배열을 이룰것입니다. 이런 점수가 되어야 꼴지도 최종 우승자가 될 수 있는지 가능성을 확인해볼 수 있습니다. 마지막으로 next 배열의 최고점수를 MAX 변수에 담습니다. 

이제는 이 MAX값과 (마지막 라운드의 점수 + N) = (arr[i] + N) 을 비교해 MAX보다 크거나 같다면 최종 우승자가 될 가능성이 있다고 볼 수 있습니다. 따라서 MAX보다 큰 값만을 세어 Answer 에 저장하면 됩니다. 저도 문제 이해하는데만 정말 오래걸렸는데 이제서야 이해가 되네요ㅠㅠ