Softeer level3 [HSAT 5회 정기 코딩 인증평가 기출] 성적 평가 Python

문제 링크 : https://softeer.ai/practice/info.do?idx=1&eid=1309 

Softeer

시간초과 코드

import sys
input = sys.stdin.readline
N = int(input())
finalRank = [0 for _ in range(N)]
for idx in range(3):
    tmp = list(map(int, input().split()))
    sortedTmp = sorted(tmp, reverse=True)
    result = [0 for _ in range(N)]
    for jdx in range(N):
        finalRank[jdx] += tmp[jdx]
        result[jdx] = sortedTmp.index(tmp[jdx]) + 1
    for r in result:
        print(r, end=" ")
    print()
sortedFinalRank = sorted(finalRank, reverse=True)
finalResult = [0 for _ in range(N)]
for idx in range(N):
    finalResult[idx] = sortedFinalRank.index(finalRank[idx]) + 1

for fr in finalResult:
    print(fr, end=" ")
print()

정답 코드

import sys
input = sys.stdin.readline
N = int(input())
finalRank = [0 for _ in range(N)]
for idx in range(3):
    result = [0 for _ in range(N)]
    tmp = list(map(int, input().split()))
    for jdx in range(N):
        finalRank[jdx] += tmp[jdx]
        result[jdx] = [jdx, tmp[jdx]]
    sortedResult = sorted(result, key=lambda x:x[1], reverse=True)
    lastResult = [0 for _ in range(N)]
    prevRank = 0
    prevValue = 0
    for jdx in range(N):
        tmp = sortedResult[jdx][1]
        if tmp != prevValue:
            prevValue = tmp
            prevRank = jdx+1
        lastResult[jdx] = sortedResult[jdx] + [prevRank]
    sortedLastResult = sorted(lastResult, key=lambda x: x[0])
    for jdx in range(N):
        print(sortedLastResult[jdx][2], end=" ")
    print()

for idx in range(N):
    finalRank[idx] = [idx, finalRank[idx]]
sortedFinalRank = sorted(finalRank, key=lambda x: x[1], reverse=True)
sortedFinalResult = [0 for _ in range(N)]

prevRank = 0
prevValue = 0
for idx in range(N):
    tmp = sortedFinalRank[idx][1]
    if tmp != prevValue:
        prevValue = tmp
        prevRank = idx+1
    sortedFinalResult[idx] = sortedFinalRank[idx] + [prevRank]

answer = sorted(sortedFinalResult, key=lambda x: x[0])
for idx in range(N):
    print(answer[idx][2], end=" ")
print()

풀이 방법

1. 3 <= N <= 10**5인 것으로 보았을 때 for문은 한 번만 적용한다.

- 이중 for문을 사용할 경우 연산이 10 ** 10이므로 10**9를 초과했기에 시간초과가 날 수 있다.

2. sorted를 여러번 사용하는데 key와 reverse를 이용한다.

3. 정렬하기 전에 리스트에 (현재 인덱스 번호, 점수, (등수))를 넣는다.

느낀점

1. 실수한 부분이 대회가 3개인데 N으로 해서 틀렸다.

- for idx in range(N)으로 했었다.

2. 역시 알고리즘을 풀 때는 내장함수를 쓰지 않는 것이 좋다.

- 이유 : 아직 시간 복잡도에 대한 이해가 부족하기 때문에 for문을 줄이거나 index함수를 사용하지 않는 것이 좋다고 본다.