[Python] 소프티어 LV.3_성적평가

소프티어 LV.3_[HSAT 5회 정기 코딩 인증평가 기출] 성적평가

import sys

n = int(sys.stdin.readline())
scores = [0]*n

def rank(score):
  result = [0]*len(score)
  for i in range(len(score)):
    cnt = 0
    for j in range(len(score)):
      if score[i] == score[j]:
        continue
      elif score[i] < score[j]:
        cnt += 1
    result[i] = cnt+1
  return result
    
        
for _ in range(n):
  score = list(map(int, sys.stdin.readline().split()))
  for i in range(len(score)):
    scores[i] += score[i]
  print(*rank(score))
print(*rank(scores))

처음에 문제에서 말한 것처럼(자신보다 높은 점수의 사람 수 세어 rank기록) 충실히 구현.
테스트케이스에서 시간초과.
참가자가 10^5명까지 가능하기 때문에..

다음은 100점이 나오는 풀이들.
내장함수 sorted쓰면 시간초과날 줄 알았는데 역시 nlogn 보장 하나보다.

1. 내장함수 sorted

import sys

n = int(sys.stdin.readline())
scores = [0]*n





def find_rank(sorted_arr):
  rank = {}
  r = 1
  for s in sorted_arr:
    if s not in rank:
      rank[s] = r
    r += 1  
  return rank


  
    
for _ in range(n):
  score = list(map(int, sys.stdin.readline().split()))
  sorted_score = sorted(score, reverse=True)
  
  rank = {}
  result = []
  rank = find_rank(sorted_score)
  for i in range(len(score)):
    result.append(rank[score[i]])
    scores[i] += score[i]
  print(*result)
  
sorted_scores = sorted(scores, reverse=True)
rank = {}
rank = find_rank(sorted_scores)
result = []
for i in range(len(scores)):
  result.append(rank[scores[i]])
print(*result)
  
  
      
  

2. 병합정렬

import sys

n = int(sys.stdin.readline())
scores = [0]*n



def merge_sort(arr):
  if len(arr) <=1 :
    return arr
  
  mid = len(arr)//2
  
  #divde
  lower = merge_sort(arr[:mid])
  higher = merge_sort(arr[mid:])

  #merge
  result = []
  l=h=0
  while l<len(lower) and h<len(higher):
    if lower[l] > higher[h]:
      result.append(lower[l])
      l += 1
    else:
      result.append(higher[h])
      h += 1
  result += lower[l:]
  result += higher[h:]

  return result



def find_rank(sorted_arr):
  rank = {}
  r = 1
  for s in sorted_arr:
    if s not in rank:
      rank[s] = r
    r += 1  
  return rank


  
    
for _ in range(n):
  score = list(map(int, sys.stdin.readline().split()))
  sorted_score = merge_sort(score)
  
  rank = {}
  result = []
  rank = find_rank(sorted_score)
  for i in range(len(score)):
    result.append(rank[score[i]])
    scores[i] += score[i]
  print(*result)
  
sorted_scores = merge_sort(scores)
rank = {}
rank = find_rank(sorted_scores)
result = []
for i in range(len(scores)):
  result.append(rank[scores[i]])
print(*result)
  

3. heapq

import sys
import heapq

n = int(sys.stdin.readline())
scores = [0]*n

def rank(score):
  rank_dict = {}
  cnt = 1
  while score:
    x, i = heapq.heappop(score)
    if -x not in rank_dict:
      rank_dict[-x] = [i, cnt]
    cnt += 1
  result = dict(sorted(rank_dict.items(), key=lambda x: x[1]))
  return result
  
    

#dict와 heapq써보기
#dict : 그 점수는 몇등이다
#heapq : 정렬 - 두개필요
#score : 입력받은 순서대로
sum_h = []
result1, result2 = [], []

for _ in range(n):
  score_h = []
  score = list(map(int, sys.stdin.readline().split()))
  for i in range(len(score)):
    heapq.heappush(score_h, [-score[i], i]) #최대힙
    scores[i] += score[i]

  result1 = rank(score_h)

  answer = []
  for i in range(len(score)):
    answer.append(result1[score[i]][1])
  print(' '.join([str(val) for val in answer]))


for j in range(len(scores)):
  heapq.heappush(sum_h, [-scores[j], j])
result2 = rank(sum_h)
answer2 = []
for j in range(len(scores)):
  answer2.append(result2[scores[j]][1])
print(' '.join([str(val) for val in answer2]))

어쨌든 요지는, 점수대로 정렬을 하고 등수를 매겨 저장할 딕셔너리를 사용하고 입력받은 점수를 key로 딕셔너리에서 value(등수)를 찾아 출력한다.
이중 for문으로 나보다 점수 높은애들 카운트하는 것보다 점수 정렬을 먼저 해주는게 빠르다. 이것이 포인트!