자료구조 및 알고리즘/프로그래머스

[프로그래머스] level1. 실패율

viamemine 2024. 6. 14. 14:11
728x90
반응형

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

실패 코드 

def solution(N, stages):
    answer = []
    ans_dict = {}
    cnt = [0] * len(stages)
    
    # 나는 도전자를 이중for문을 돌면서 찾았는데 ... 
    for i in range(len(stages)): # 0 1 2 3 4 5 6 7
        for j in range(len(stages)): # 0 1 2 3 4 5 6 7
            if (i+1) == stages[j]:
                cnt[i] += 1
                
        if i == 0:
            ans_dict[i+1] = (cnt[i] / len(stages))
        elif i < N: # 1 2 3 4
            ans_dict[i+1] = (cnt[i] / (len(stages)-sum(cnt[:i])))
        
    ans_dict = sorted(ans_dict.items(), key=lambda x: -x[1]) # O(NlogN)
    
    for k, v in ans_dict:
        answer.append(k)
    return answer

위의 코드는 출력은 잘 나왔지만, 시간 초과와 런타임 에러가 다수 발생

 

 

💥 성공 코드 

def solution(N, stages):
    
    challenger = [0] * (N+2) # stage별 도전자 수 (0번 idx, 마지막 stage 성공자)
    for stage in stages:
        challenger[stage] += 1
    
    fails = {} # stage별 실패한 사용자 수 계산
    total = len(stages)
    
    # 각 stage를 순회하며, 실패율 계산
    for i in range(1, N+1):
        if challenger[i] == 0: # 도전한 사람이 없는 경우, 실패율은 0
            fails[i] = 0 
        else:
            fails[i] = challenger[i] / total
            total -= challenger[i] # 다음 stage 실패율을 구하기 위해 현재 stage 인원을 뺌
            
    result = sorted(fails, key=lambda x: -fails[x]) # value로 key 정렬
    return result

 

 

실패 코드에서 나는 도전자를 이중for문을 돌면서 찾았는데 

성공 코드를 보면 for문 한 번 돌면서 찾는다 ! 

728x90