[Softeer] 성적 평가

문제

현주는 N명의 인원이 참여하는 프로그래밍 스터디 그룹을 이끌고 있다.

현주는 스터디를 위해 대회를 세 개 개최하였고, 모든 구성원이 각 대회에 참여하였다. 참가자는 각 대회에서 0 이상 1,000 이하의 정수인 점수를 얻는다. 한 대회에서 둘 이상의 참가자가 동점이 나오는 경우도 있을 수 있다.

현주는 각 대회별 등수 및 최종 등수를 매기고 싶다. 등수는 가장 점수가 높은 사람부터 1등, 2등, ···, N등의 순서대로 붙는다. 만일 동점이 있을 경우 가능한 높은 (등수의 수가 작은) 등수를 부여한다. 즉, 점수가 내림차순으로 10,7,6,6,4의 순서일 경우, 6점을 받은 두 사람은 공동 3등이 되고, 그 다음 순서인 4점을 받은 사람은 5등이 된다. 이 규칙을 다르게 표현하면 다음과 같다: 각 사람마다 “나보다 점수가 큰 사람”의 수를 세어 1을 더한 것이 자신의 등수가 된다. 대회별 등수는 각 대회에서 얻은 점수를 기준으로 하며 최종 등수는 세 대회의 점수의 합을 기준으로 한다.

각 참가자의 대회별 등수 및 최종 등수를 출력하는 프로그램을 작성하시오.

제약조건

3 ≤ N ≤ 100,000

입력형식

첫째 줄에 참가자의 수를 나타내는 정수 N이 주어진다.
이어 세 개의 줄에 각 대회의 결과를 나타내는 N개의 정수가 주어진다. 이중 i번째 정수는 그 대회에서 i번째 사람이 얻은 점수를 의미한다.

출력형식

첫 세 개의 줄에는 각 참가자의 대회별 등수를 출력한다. 즉 이중 c번째 줄의 i번째 정수는 c번째 대회에서의 i번째 사람의 등수를 의미한다.
이어 새로운 줄에 같은 형식으로 각 참가자의 최종 등수를 출력한다.

입력예제 1

3
40 80 70
50 10 20
100 70 30

출력예제 1

3 1 2
1 3 2
1 2 3
1 2 3

나의 풀이

처음에 단순히 중첩 for문으로 구성하여 행에서 인덱스보다 큰 값을 count 했는데, N의 최대 범위가 100,000 이므로 복잡도가 O(N^2)이 나와 시간초과가 발생했다.

시간 복잡도를 줄이기 위해 이진 탐색을 사용하기로 했다. (이진 탐색 복잡도 : logN)
이진 탐색은 배열이 정렬되어 있을 때 가능하므로 정렬은 파이썬 표준 정렬 라이브러리 사용했다.
최악의 경우도 복잡도는 NlogN이다.

문제는 점수가 동점일 경우이였다.
같은 점수일 경우 check 함수를 따로 두어, 같은 점수일 때 가장 앞의 index 위치를 반환하여 이를 해결했다.

아래의 최종 O(NlogN)의 복잡도의 코드를 구현했다.

import sys
import copy

N = int(input())
data = []
result = []
copyarr = []

for _ in range(3) :
    data.append(list(map(int,input().split())))

for i in range(N) :
    result.append(data[0][i] + data[1][i] + data[2][i])
data.append(result)

def rank(arr) :
    copyarr = copy.deepcopy(arr)
    arr.sort(reverse = True)    
    for i in copyarr :
        binarySearch(0, N - 1, arr, i)


def binarySearch(start, end , arr, i) :
    mid =  (start + end) // 2
    if arr[mid] == i :
        if arr[mid - 1] == i :
            count = check(arr, i, mid, 0)
            print(mid - count + 1, end = " ")
        else :
            print(mid + 1, end = " ")
    elif arr[mid] < i :
        binarySearch(0, mid - 1, arr, i)

    else :
        binarySearch(mid + 1, end, arr, i)

def check(arr, i, mid, count) :
    while(arr[mid - 1] == i) :
        mid -= 1
        if mid < 0 :
            break
        count += 1
    return count
        
for i in range(4) :

    rank(data[i])
    if i != 3 :
        print()

시간과 메모리도 여유롭게 성공할 수 있었다.

import sys

n = int(input())
score = []
for _ in range(3) :
    score.append(list(map(int, input().split())))

total_score = []
for i in range(n) :
    total_score.append(score[0][i] + score[1][i] + score[2][i])

score.append(total_score)
score_oringal = [item[:] for item in score]

for i in score :
    i.sort(reverse = True)

def count(index, answer, score) :
    count = 0
    while(score[index - 1] == answer) :
        count += 1
        index -= 1
        if index == 0 :
            break
    return count

def binarysearch(start, end, score, answer) :
    mid = (start + end) // 2
    if score[mid] == answer :
        if score[mid - 1] == answer :
            return mid - count(mid, answer, score) + 1
        else :
            return mid + 1
    elif score[mid] > answer :
        return binarysearch(mid + 1, end, score, answer)
    else :
        return binarysearch(start, mid - 1, score, answer)

for i in range(4) :
    for j in score_oringal[i] :
        print(binarysearch(0, n - 1, score[i], j), end = " ")
    
    if i == 3 : break
    print()

깊은 복사에 deepcopy보다 슬라이싱이 더 빠르다는 것을 확인하고 두번 째 풀땐 수정하여 풀었다.