2019 KAKAO BLIND RECRUITMENT > 실패율 -Python, 딕셔너리 정렬

 

 

주소

 

 

풀이 - 나의 생각

스테이지별 실패자 수를 세고

 

실패율을 구한다.

 

실패율은

 

스테이지 실패자가 0인 경우에는 0으로 넣어주면 되고

 

그 외에는,

 

스테이지별 실패자를 나머지 사용자로 나눠주면 된다.

 

이 나머지 사용자는

 

처음에는 stages의 길이로 시작해서

 

실패자 수를 빼가면 된다.

 

처음에는 stage_cnt[idx:]로 구했는데

 

이럴경우 매번 합을 다시 구해야하기에 누적합 방식으로 바꿨다.

 

그 후에는 실패율 구한 걸 value 기준으로 정렬해서

 

key 값을 반환해주면 끝난다.

 

반환하는 방식이

 

1. 명시적으로 value값으로 정렬 후, key값으로 정렬

 

# 실패율 기준 정렬 (내림차순), 실패율이 같으면 스테이지 번호 기준 오름차순
sorted_stages = sorted(fail_rates.items(), key=lambda x: (-x[1], x[0]))
    
return [stage[0] for stage in sorted_stages]

 

 

2. 그냥 딕셔너리가 제공하는 기본 정렬을 사용하는 방법

 

# 실패율 기준 정렬 (내림차순), 실패율이 같으면 스테이지 번호 기준 오름차순    
return sorted(fail_rates, key=lambda x: fail_rates[x], reverse = True)

 

코드 효율성 차이

• 수행 시간:
  두 코드 모두 실패율 계산의 시간 복잡도는 O(N), 정렬의 시간 복잡도는 O(Nlog⁡N)로 동일.
• 메모리 사용:
  1의 코드가 fail_rates.items()를 정렬하므로, 약간의 추가 메모리를 사용합니다. 2의 코드는 키만 정렬하므로 메모리 사용이 약간 더 적음.

 

• 1의 코드의 장점:
  실패율이 같은 경우에도 스테이지 번호 오름차순이 명확하게 보장됨.
• 2의 코드의 장점:
  간결하고 메모리 효율적.

 

 

 

코드

 

def solution(N, stages):
    # 스테이지별 도달한 사용자 수
    stage_cnt = [0] * (N + 2)
    
    for stage in stages:
        stage_cnt[stage] += 1
    
    # 실패율 계산
    total_users = len(stages)
    fail_rates = {}
    
    for stage in range(1, N + 1):
        if total_users > 0: # 0을 나눌 수 없음
            fail_rates[stage] = stage_cnt[stage] / total_users
            total_users -= stage_cnt[stage]
        else:
            fail_rates[stage] = 0 
    
    # 실패율 기준 정렬 (내림차순), 실패율이 같으면 스테이지 번호 기준 오름차순
    sorted_stages = sorted(fail_rates.items(), key=lambda x: (-x[1], x[0]))
    
    return [stage[0] for stage in sorted_stages]

 

 

 

 

 

 

 

다음에 또 봐요