백준 2790번 파이썬 코드 답안

문제

권위를 자랑하는 레이싱 대회 F7이 열릴 예정이다. F7은 드라이버의 순위가 자주 바뀌기 때문에 사람들에게 인기가 아주 많다. 상근이는 F7 레이싱의 엄청난 팬이지만, 마지막 레이싱과 중간고사가 겹쳐서 갈 수 없게 되었다.

지금은 마지막 레이싱을 제외한 나머지 레이싱이 모두 종료된 상황이다. 상근이는 우승을 할 수 있는 사람의 수를 알아보려고 한다. F7의 우승자는 각 레이싱을 통해서 얻은 점수의 합이며, 점수가 가장 높은 사람이 우승을 하게 된다.

마지막 레이싱에서 1등을 한 사람은 N점을 얻게 되고, 2등은 N-1점, ..., 꼴등은 1점을 얻게 된다. 각 레이싱에서 두 드라이버의 등수가 같은 경우는 없다.

마지막 레이싱을 하기 바로 전에 각 드라이버의 점수가 주어졌을 때, 우승을 할 가능성이 있는 사람의 수를 구하는 프로그램을 작성하시오. 만약 점수의 합이 가장 큰 사람이 여러 명이라면, 여러명 다 우승자이다.

입력

첫째 줄에 F7에 참가하는 드라이버의 수 N (3 ≤ N ≤ 300,000)이 주어진다.

다음 N개 줄에는 각 드라이버가 마지막 레이싱을 하기 전까지 얻은 점수 Bi가 주어진다. (0 ≤ Bi ≤ 2,000,000, i = 1, ..., N)

출력

첫째 줄에 F7을 우승할 가능성이 있는 사람의 수를 출력한다.

문제풀이

살펴봐야 하는 드라이버의 수를 살펴보면 N이 최대 300,000까지 들어올 수 있다. 이게 뭘 뜻하냐면, 시간 복잡도가 N^2이 되버리면 절대로 시간 이내에 통과할 수 없다는 것을 뜻한다. 따라서 시간 복잡도 O(n)을 만족하면서 진행할 수 있도록 해야한다. 그렇다면 어떻게 해야할까?

가장 쉬운 아이디어부터 생각해본다. 1등은 거의 1등할 확률이 높다. 그렇다면 초점은 꼴찌에 맞추어야 한다. 그렇다면 꼴찌가 1등이 되려면 어떻게 해야할까? 꼴지는 항상 마지막 레이스에서 1등을 해야하고, 1등은 꼴지를 해야지 현재 꼴찌가 레이스가 끝났을 때 1등이 될 가능성이 있다.

이번 문제를 풀 때 사용했던 생각은 바로 위의 생각이었다. 먼저 전체 점수를 리스트에 받은 후, 정렬을 한다. 정렬한 후에 순서대로 점수를 나누어줬다. 예를 들어, 5명이 참가한다면 꼴지에게는 5점을, 그 다음 꼴지에게는 4점을, 1등에게는 1점을. 이렇게 점수를 나누어주고, 현재 전체 리스트 중에서 가장 큰 값을 미리 저장해둔다. 

이후, 비교를 시작한다. 0번 선수(꼴지)가 1등을 했을 때 값이 리스트의 값들 중 최고값보다 크거나 같다면 꼴지 선수는 1등을 할 수 있다. 그리고 그 다음 선수 등수의 선수가 1등할 수 있는지를 따져본다. 그 다음 선수는 2등을 한다고 가정을 했을텐데, 1등을 한다고 가정을 해주면 해당 등수의 선수에게 1점을 더 해준다. 그 상태에서 전체 리스트 값들 중 최고값보다 크거나 같은지를 따져본다. 

그리고 그 다음 선수의 값은 3등을 한다고 가정했을 때 가진 값인데, 1등을 한다고 가정을 해주면 해당 등수의 선수에게 2점을 더 해주면 되고, 이 값으로 비교를 해준다.

위와 같은 순서를 반복하게 되면 전체 리스트를 한번만 둘러 보는 것으로 해결이 가능하다. 물론, 정렬 자체의 시간복잡도가 O(nlogn)이기 때문에 목표했던 시간 복잡도인 O(n)을 달성하지는 못했지만, 문제를 해결하기에는 충분하다. 코드는 아래를 참고.

import sys
t = int(sys.stdin.readline().rstrip())
my_list = []
for i in range(t) :
    my_list.append(int(sys.stdin.readline().rstrip()))
my_list = sorted(my_list)
for i in range(len(my_list)) :
    my_list[i] = my_list[i] + t
    t -=1
my_cnt = 0
max_v = max(my_list)
for i in range(len(my_list)-1) :
    if my_list[i] >= max_v :
        my_cnt +=1
    t += 1
    my_list[i+1] += t

if my_list[-1] > max_v :
    print(my_cnt+1)
else :
    print(my_cnt)