happenundo 2023. 4. 14. 14:29
728x90
 

프로그래머스

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

programmers.co.kr

간단한 구현 문제다.

 

각 스테이지마다 실패율을 구해서 실패율이 큰 순서대로 내림차순 정렬한 리스트를 반환하면 되는 문제.

처음에는 입력된 stages 배열에서 for문을 돌면서 실패율을 구하기 위한 스테이에 도달한 플레이어 수와 스테이지에 도달했지만 클리어하지 못한 플레이어 수를 스테이지에 맞게 더해주려고 했다.

하지만 이 경우, stages 배열의 길이가 최대 200,000이고, 스테이지의 개수도 최대 500개이므로 무조건 시간초과가 날것 같다는 생각이 들었고, 풀이를 바꿨다.

 

첫 풀이

def solution(N, stages):
    answer = []
    fail_rates = [(i, 0, 0) for i in range(1, N+1)] 
    # (a, b, c) = (a번 스테이지, 스테이지에 도달했지만 아직 클리어하지 못한 플레이어 수, 스테이지에 도달한 플레이어 수)
    
    for player in stages:
        if player > N: # 모든 스테이지를 클리어한 플레이어
            fail_rates[N][2] += 1

 


두번째 풀이

collections 라이브러리의 counter 모듈을 사용한다.

스테이지 별 플레이어의 수를 counter 모듈을 사용해서 개수를 받아온다.

그리고 fail_rates라는 2차원리스트에

[스테이지, 스테이지에 도달했지만 아직 클리어하지 못한 플레이어 수, 스테이지에 도달한 플레이어 수]를 저장한다.

저장한 후, answers 리스트에 [스테이지, 스테이지별 실패율]을 저장하고, 

lambda 식을 이용해서 스테이지별 실패율을 내림차순으로 정렬하고, 같을 경우, 스테이지 번호로 오름차순 정렬한다.

 

from collections import Counter

def solution_1(N, stages):
    answers = [[0,10]]
    fail_counts = Counter(stages)
    fail_counts_list = list(zip(fail_counts.keys(), fail_counts.values()))
    fail_rates = [[i, 0, 0] for i in range(N+1)] 
    # [a, b, c] = [a번 스테이지, 스테이지에 도달했지만 아직 클리어하지 못한 플레이어 수, 스테이지에 도달한 플레이어 수]

    
    for i in range(1, N+1):
        fail_rates[i][1] = fail_counts[i] # 스테이지에 도달했지만 아직 클리어하지 못한 플레이어의 수
        fail_rates[i][2] = sum([count[1] for count in fail_counts_list if count[0] >= i])
        # 스테이지에 도달한 플레이어의 수
        

        
        if fail_rates[i][2] == 0: # 스테이지에 도달한 플레이어의 수가 없는 경우 실패율은 0
            answers.append([i,0])
        else:
            answers.append([i,fail_rates[i][1] / fail_rates[i][2]])
            
        
    answers.sort(key = lambda x: (-x[1], x[0]))
    return [answer[0] for answer in answers[1:]]

 

이렇게 푸니까 정답이 나왔다.


하지만 여기서 fail_rates라는 리스트는 사실 필요 없다.

코드 이해도를 높이기 위해 추가한 리스트라서 코드를 최대한 단순하게 만들면 밑 코드처럼 나온다.

 

최종 코드

 

from collections import Counter

def solution(N, stages):
    answers = [[0,10]]
    fail_counts = Counter(stages)
    fail_counts_list = list(zip(fail_counts.keys(), fail_counts.values()))

    for i in range(1, N+1):
        notclear_player = fail_counts[i] # 스테이지에 도달했지만 아직 클리어하지 못한 플레이어의 수
        reached_player = sum([count[1] for count in fail_counts_list if count[0] >= i])
        # 스테이지에 도달한 플레이어의 수
        
        if reached_player == 0: # 스테이지에 도달한 플레이어의 수가 없는 경우 실패율은 0
            answers.append([i,0])
        else:
            answers.append([i,notclear_player / reached_player])
            
        
    answers.sort(key = lambda x: (-x[1], x[0]))
    return [answer[0] for answer in answers[1:]]

 

728x90