[Python] 프로그래머스 | 실패율
요즘 파이썬으로 알고리즘 문제를 풀고 있다.
파이썬 다운 코드 보다는.. 스스로 생각한 로직으로 솔루션을 제시하는 것에 집중하고 있다.
코드에 주석이 섞여있는데 요구사항을 읽으며 주석을 간단히 달아두는 게 도움이 많이 된다.
동료들과 우테코 최종 테스트 대비 스터디를 하며 아직은 주석을 달아가며 구현하는게 필요하다고 느꼈다.
아직 내가 작성한 코드를 한 눈에 알아보는 능력이 부족하기도 하고,
요구사항을 분석하며 필요한 로직을 주석으로 달아 구현해 나가면 좀 더 세세하게 설계를 고민할 수 있는 것 같다.
def solution(N, stages):
answer = [] # 실패율이 높은 스테이지 내림차순
# 실패율 = 스테이지 도달&아직 클리어x 플레이어 수 / 스테이지 도달한 플레이어 수
# N : 전체 스테이지 개수
# stages : 사용자가 현재 멈춰있는 스테이지 번호, N+1은 마지막스테이지 클리어한 사용자
# stages 돌면서 실패율 계산
fail_dic = dict()
max_stage = N + 1
for i in range(1, max_stage):
total_player = 0
yet_player = 0
for stage in stages:
if stage >= i:
total_player += 1
if stage == i:
yet_player += 1
if total_player == 0:
fail_dic[i] = 0
else:
fail_dic[i] = yet_player / total_player
# 내림차순으로 정렬
# 실패율이 같으면 작은 번호의 스테이지가 먼저온다
# 스테이지에 도달한 유저가 없으면 실패율 0으로 정의
sorted_lst = sorted(fail_dic.items(), key= lambda item:item[1], reverse=True)
answer = list(item[0] for item in sorted_lst)
return answer
문제를 풀면서 두 가지 문제점이 있었다.
런타임 오류
채점을 하면 몇몇 테스트에서 런타임 오류가 발생했는데,
이는 스테이지에 도달한 플레이어(total_player)가 없는 경우 0으로 정의하지 않아
스테이지에 도달했으나 클리어하지 못한 플레이어 수 / 스테이지에 도달한 총 플레이어 수
위 계산식이 0 / 0 이 되어 오류가 발생한 것이다.
아래는 오류가 발생한 코드이다.
# stages 돌면서 실패율 계산
fail_dic = dict()
for i in range(1, N+1):
total_player = 0
yet_player = 0
for stage in stages:
if stage >= i:
total_player += 1
if stage == i:
yet_player += 1
fail_dic[i] = yet_player / total_player # <-여기서 런타임 오류 발생!
문제를 해결하기 위해 간단히 else 문을 추가해 계산식에 도달하기 전,
스테이지에 도달한 플레이어(total_player)가 0인 경우 실패율을 0으로 정의하도록 수정했다.
if total_player == 0:
fail_dic[i] = 0
else:
fail_dic[i] = yet_player / total_player
시간 복잡도
지금까지 알고리즘 문제를 풀면서 시간 복잡도를 크게 고려하지 않았다.
하지만 이번 문제의 실행 속도를 보니 이제는 시간복잡도를 다시 공부하고, 설계 시 꼭 고려해야겠다고 느꼈다.
내 코드에서 스테이지에 도달한 플레이어(total_player)를 구하기 위해 for문을 돌며 일일히 계산하고 있다.
Collections.counter(len(stages)) 를 사용했다면 O(N*M) -> O(M)으로 줄일 수 있다.
- M: stages의 길이. (사용자의 수)
이후 사용자 수를 구해 다음 루프를 돌기 전, 사용자의 수 - 스테이지에 도달했지만 클리어하지 못한 사용자의 수 를 계산하면, 다음 스테이지에 도달한 사용자의 수를 구할 수 있다.
앞으로는 자료구조와 시간 복잡도에 대해 공부해 적용하는 것을 목표로 해야겠다 :)