[파이썬(python)] 정렬 문제 실패율

https://programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

모든 스테이지에 대한 실패율을 계산하고 각 번호를 실패율의 내림차순으로 정렬하는 문제이다

 

실패율까지 잘 계산했는데...

그러나 실패율의 내림차순으로 리스트를 출력하는 방법을 잘 모르겠더라.

 

원래 코드

def solution(N, stages):
    rate_list = []

#실패율 리스트
    stages.sort()

#오름차순 정렬
    for i in range(1,N+1):
        count_i = stages.count(i) #클리어하지 못한 사람 수

        count_try = 0 #도전한 사용자 수
        for j in stages:
            if j>=i:
                count_try += 1
        rate = count_i/count_try
        rate_list.append(rate) #리스트에 실패율 추가

    sort_list = sorted(rate_list, reverse=True)
        
    print(sort_list)
    print(rate_list)
    return answer

음 ... 내림차순 정렬하기 전의 배열과 정렬한 뒤의 배열을 비교해서 다시 리스트를 만들어야 하나 고민하다가 아무래도

이게 아닌 것 같아 생각해봤다

답은 매우 간단 ㅜㅜ 리스트에 실패율과 스테이지번호를 리스트로 추가한 뒤에 실패율 순으로 내림차순 정렬하면 된다

 

def solution(N, stages):
    rate_list = []
    answer = []
    stages.sort()
    for i in range(1,N+1):
        count_i = stages.count(i)
        count_try = 0
        for j in stages:
            if j>=i:
                count_try += 1
        rate = count_i/count_try
        rate_list.append([rate, i])
    rate_list.sort(key = lambda x:x[0], reverse=True)
    
    answer = [i[1] for i in rate_list]
    
    return answer

 

그러나 런타임 에러로 인해 100점 중에 70점 밖에 못받았다.  시간 복잡도가 N*N이고 공간 복잡도도 두개의 배열을 사용해서 그런듯 하다. 실패율을 조금 더 효율적으로 계산하는 방법을 생각해봐야겠다.

 

개선한 코드는 answer 배열 하나만 이용하고 count_try 계산하는 것도 단순화 했다.

 

def solution(N, stages):
    answer = []
    count_try = len(stages)
    for i in range(1,N+1):
        count_i = stages.count(i)
        rate = count_i/count_try
        answer.append([rate, i])
        count_try -= count_i
        
    answer.sort(key = lambda x:x[0], reverse=True)
    
    answer = [i[1] for i in answer]
    
    return answer

 

근데 이것도 런타임 에러남.. ㅜㅜ 다시 보니 count_try가 0일 경우에 런타임에러가 나는 것이었다

 

최종 코드는 이것이다. 공부하기에 아주 좋은 문제였던 것 같다

def solution(N, stages):
    answer = []
    count_try = len(stages)
    for i in range(1,N+1):
        count_i = stages.count(i)
        if count_try == 0:
            rate = 0
        else:
            rate = count_i/count_try
        answer.append([rate, i])
        count_try -= count_i
        
    answer.sort(key = lambda x:x[0], reverse=True)
    
    answer = [i[1] for i in answer]
    
    return answer