Q25. 실패율 (2019 카카오 신입 공채 기출)

코딩테스트 연습 - 실패율 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 실패율

 

10분짜리 타이머를 켜놓고 어떻게 풀지 고민했고, 실패율을 구하는 과정에서 O(len(stage)^2)의 시간복잡도가 필요하다고 느꼈다. 내가 처음 생각한 아이디어는 길이 N의 카운트 배열을 2개 만들고 (아직 클리어 못한 사람 수, 스테이지를 도달한 사람 수) stage배열을 iterate over하면서 카운트 배열을 완성해나가고 나중에 실패율을 한꺼번에 계산하는거였는데, 공간적으로도 비효율적일뿐더러 실패율 계산 후에 어떻게 정렬해야될지 감이 안잡혀서(ㅠ) 결국 답지를 봤다.

 

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

 

첫 번째 스테이지는 모든 사람들이 도달했을거니까 len(stages)만큼의 플레이어들이 도달했을 것이다.

두 번째 스테이지는 (모든 사람들 수 - 첫 스테이지를 도달한 사람 수)만큼의 플레이어들이 도달했을 것이고

세 번째 스테이지는 (모든 사람들 수 - 첫 스테이지 도달 수 - 두 번째 스테이지 도달 수)일 것이다.

그래서 처음에 remaining(남은 사람수) 변수를 len(stages)로 초기화하고 fail(실패율)을 players / remaining으로 구한 뒤에 remaining에서 players를 뺀 것이다.

 

그리고 python sort는 stable하기 때문에 기존에 스테이지 넘버 순으로 정렬되어 있던 answer배열을 저렇게 정렬시키면 문제의 조건이(실패율이 같으면 스테이지 넘버 순으로 나열하라는 것) 자동으로 충족된다.

 

이 문제를 20분 안에 풀어야 된다니.. 혼자 풀라고했으면 1시간은 걸렸을 것이다. 꾸준히 연습해서 시간을 단축시키자.