[이코테] 정렬 문제 - 실패율 python

난이도 : ●○○ | 풀이 시간 : 20분 | 시간 제한 : 1초 | 메모리 제한 : 128MB | 기출 : 2019 카카오 신입 공채 1차

 

문제

• 신규 사용자와 기존 사용자 사이의 스테이지 차이를 줄이려는 게임 개발자를 돕자.
• 전체 스테이지 개수 N, 플레이어가 멈춰있는 스테이지 번호가 담긴 배열 stages가 주어진다.
• 실패율이 높은 것부터 내림차순으로 스테이지의 번호가 담긴 배열을 return하는 함수를 완성하라.
• 실패율을 구하는 식
  • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수

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

 

제한사항

• 스테이지 개수 N은 1이상 500이하다.
• stages의 길이는 1이상 200,000 이하다.
• stages에는 1 이상 N+1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지 번호를 의미한다.
  • 단, N+1은 마지막 스테이지(N번째 스테이지)까지 클리어한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 한다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0이다.

 

입출력예시

N	stages	result
5	[2,1,2,6,2,4,3,3]	[3,4,2,1,5]
4	[4,4,4,4,4]	[4,1,2,3]

입출력예시에 대한 설명

• 1번 스테이지에 도달한 사람 : 8명, 그 중 클리어하지 못한 사람 : 1명
  • 1번 스테이지의 실패율 = 1/8
• 2번 스테이지에 도달한 사람 : 7명, 그 중 클리어하지 못한 사람 : 3명
  • 2번 스테이지의 실패율 = 3/7
• 같은 방식으로
  • 3번 스테이지의 실패율 = 2/4
  • 4번 스테이지의 실패율 = 1/2
  • 5번 스테이지의 실패율 = 0/1
• 각 스테이지 번호를 실패율 내림차순으로 정렬한 결과
  • [3,4,2,1,5]

 

아이디어

• 각 스테이지의 실패율을 구한다.
  
  • 실패율 : 아직 클리어하지 못한 사람 수 / 스테이지에 도달한 사람 수
    • 1부터 n까지 i를 1씩 증가시키면서
      • 아직 클리어하지 못한 사람 수 : stages.count(i)
      • 스테이지에 도달한 사람 수 : stages에 저장된 값 >= i를 만족하는 사람 수
        • i를 1씩 증가시키는 것으로 낮은 스테이지부터 몇명이 머물러있는지 알 수 있다.
          • 제일 낮은 1단계에 도달한 사람 수 == 전체 플레이어 수
          • 2단계에 도달한 사람 수 == 전체 플레이어 수 - 1단계에 머물러 있는 사람
          • 한 스테이지의 실패율을 계산한 뒤, 그 스테이지에 머물러 있는 사람 수를 빼면 다음 스테이지에 도달한 사람 수를 구할 수 있다.
    • 실패율을 계산할 때 분모가 0이 되는 경우를 신경써줘야 한다.
• (실패율, 스테이지 번호)를 리스트에 저장하고 실패율의 내림차순으로 정렬한다.
• 스테이지 번호만 배열에 저장해서 return한다.

 

코드

def solution(N, stages):
    answer = []
    length = len(stages)
    
    for i in range(1,N+1):
    	# 해당 스테이지에 머물러있는 사람 수
        # 1번부터 N까지 1씩 증가하므로
        # 낮은 스테이지부터 높은 스테이지순으로 머물러있는 사람수를 알 수 있음
        cnt = stages.count(i)
        
        if length==0:
            fail = 0
        else:
            fail = cnt/length
            
        # 실패율, 인덱스를 리스트에 추가
        answer.append((fail, i))
        length -= cnt
        
    # 실패율의 내림차순으로 정렬
    answer.sort(key=lambda x:-x[0])
    # 인덱스(=스테이지 번호)만 뽑아냄
    answer = [i[1] for i in answer]
    
    return answer

 

 

후기

• 카카오문제는 난이도가 낮게 설정되어있어도 뭔가 어려운 것 같다... 

 

출처

이것이 취업을 위한 코딩테스트다 with python