[파이썬] 프로그래머스 LV1 실패율

프로그래머스 실패율

나의 풀이

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

보기에는 깔끔한 코드지만 결과가 지저분한 코드였다.

• 매개변수 i를 1부터 전체 스테이지의 개수 N번 만큼 돌린다.
• 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 비었을 때 size == 0 실패율이 0이므로 스테이지 마다 실패율 0 을 스테이지 넘버와 함께 튜플로 넣어준다.
• 아닐경우 각 스테이지의 갯수를 카운트해서
• 남아있는 사람들의 갯수로 나눠 실패율을 구하고 스테이지 넘버와 함께 튜플로 넣어준다.
• 실패율x[1]이 높은 스테이지부터 내림차순으로 스테이지번호 x[0]으로 정렬한다.

다른 사람의 풀이

def solution(N, stages):
	# stages에는 1 이상 N + 1 이하의 자연수가 담겨있다
    answer = [] # [stage]
    fail = [] # [(stage, failure_rate)]
    
    # step 0: N+2개 만큼의 0 이 있는 리스트 준비
    # + 1 : stage 0
    # + 1 : stage N + 1
    # solution(5,[2, 1, 2, 6, 2, 4, 3, 3]) 일 때
    # [0, 0, 0, 0, 0, 0, 0] 을 만든다
    info = [0] * (N + 2) 
    
    # step 1: stages에서 나온 stage를 인덱스로 활용해서 그 값이 나올 때마다 1 을 더해준다
    # stages의 마지막 3 까지 돌았을 때 결과: [0, 1, 3, 2, 1, 0, 1]
    for stage in stages:
        info[stage] += 1
        
    # step 2 : 
    for i in range(N):
        be = sum(info[(i + 1):]) # 남아있는 인원 수
        yet = info[i + 1]  #+1을 더해줌.. 왜냐면 stage0는 없기 때문. 진짜 시작 되는 stage부터 카운트 해준다.
        if be == 0:
            fail.append((str(i + 1), 0))
        else:
            fail.append((str(i + 1), yet / be))
            
    # step 3 : 실패율에 따라 stage number 정렬
    for item in sorted(fail, key=lambda x: x[1], reverse=True):
        answer.append(int(item[0]))
    return answer

count() 를 stage number마다 안해준게 큰 차이 같다. 이게 O(n^2)를 만든듯함.
이 코드의 step 1은 count()를 안쓰고 그냥 stages를 훑기 때문에 O(n)이 된다.
이렇게 0으로 리스트로 만들어서 인풋 리스트를 한번 훑으며 그 값을 index로 사용해서 +1을 해주는 방법을 이번에 배운 듯!

성능

	나의 풀이	다른 사람의 풀이
테스트 1 〉	통과 (0.02ms, 10.3MB)	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.24ms, 10.1MB)	통과 (0.10ms, 10.3MB)
테스트 3 〉	통과 (77.42ms, 10.5MB)	통과 (1.83ms, 10.5MB)
테스트 4 〉	통과 (427.23ms, 10.7MB)	통과 (6.04ms, 10.8MB)
테스트 5 〉	통과 (1694.18ms, 14.9MB)	통과 (12.67ms, 14.9MB)
테스트 6 〉	통과 (1.29ms, 10.2MB)	통과 (0.19ms, 10.3MB)
테스트 7 〉	통과 (10.53ms, 10.1MB)	통과 (0.66ms, 10.6MB)
테스트 8 〉	통과 (375.64ms, 10.8MB)	통과 (6.22ms, 10.8MB)
테스트 9 〉	통과 (1929.31ms, 15MB)	통과 (18.73ms, 15MB)
테스트 10 〉	통과 (185.05ms, 10.7MB)	통과 (6.21ms, 10.8MB)
테스트 11 〉	통과 (527.22ms, 10.9MB)	통과 (7.57ms, 10.8MB)
테스트 12 〉	통과 (237.97ms, 11.3MB)	통과 (9.47ms, 11.3MB)
테스트 13 〉	통과 (504.54ms, 11.2MB)	통과 (11.77ms, 11.3MB)
테스트 14 〉	통과 (0.03ms, 10.1MB)	통과 (0.07ms, 10.3MB)
테스트 15 〉	통과 (21.60ms, 10.6MB)	통과 (4.39ms, 10.5MB)
테스트 16 〉	통과 (5.11ms, 10.3MB)	통과 (2.20ms, 10.5MB)
테스트 17 〉	통과 (12.24ms, 10.5MB)	통과 (8.25ms, 10.5MB)
테스트 18 〉	통과 (10.51ms, 10.1MB)	통과 (2.12ms, 10.3MB)
테스트 19 〉	통과 (1.92ms, 10.2MB)	통과 (0.45ms, 10.5MB)
테스트 20 〉	통과 (9.61ms, 10.3MB)	통과 (3.09ms, 10.4MB)
테스트 21 〉	통과 (15.92ms, 10.9MB)	통과 (11.44ms, 10.8MB)
테스트 22 〉	통과 (1406.06ms, 18.3MB)	통과 (14.24ms, 18MB)
테스트 23 〉	통과 (10.75ms, 11.6MB)	통과 (20.21ms, 11.5MB)
테스트 24 〉	통과 (67.14ms, 11.5MB)	통과 (12.74ms, 11.6MB)
테스트 25 〉	통과 (0.01ms, 10.1MB)	통과 (0.03ms, 10.3MB)
테스트 26 〉	통과 (0.01ms, 10.1MB)	통과 (0.02ms, 10.3MB)
테스트 27 〉	통과 (0.01ms, 9.96MB)	통과 (0.03ms, 10.4MB)

유난히 시간이 오래걸린 테스트들 에서는 10배의 차이가 났다.