[카카오] 2019 KAKAO BLIND RECRUITMENT 1차 풀이 – 실패율
이 포스팅에서는 2019 카카오 블라인드 채용 1차 문제인 ‘오픈채팅방’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/42889에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.
공식 풀이는 링크를 참조하시기 바랍니다.
실패율
출처 : 2019 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/42889
카테고리 : Greedy
난이도 : 쉬움
문제 설명
각 유저들이 최종적으로 도달한 스테이지의 넘버가 주어진다. 각 스테이지별로 (스테이지에 머물러 있는 사람 / 스테이지에 도달했던 모든 사람)을 실패율로 정의한다.
실패율이 높은 스테이지부터 낮은 스테이지까지 내림차순으로 출력하고, 같은 실패율을 가지는 것이 있다면 스테이지 번호의 오름차순으로 정렬해서 출력.
문제 풀이
각 스테이지 넘버별로 해당 스테이지에 머물러 있는 사람들의 수를 카운트한다.
스테이지 넘버가 작은 것부터 큰 것 순서로 실패율을 계산한다. 맨 처음에는 누적 인원을 N으로 두고, 매 스테이지마다 스테이지에 머물러 있는 인원을 빼면 다음 스테이지에 도달했던 모든 인원수를 구할 수 있다.
정렬 기준이 실패율은 내림차순, 스테이지 번호는 오름차순이므로 실패율을 저장할 때 -1을 곱해서 저장한 후 오름차순 정렬시키면 쉽게 정렬할 수 있다.
정답 코드
def solution(N, stages): dic = {} # 각 스테이지 별로 실패한 사용자의 수를 집계 for i in range(len(stages)): if stages[i] not in dic: dic[stages[i]] = 1 else: dic[stages[i]] += 1 percentile = [] cnt = 0 # 각 스테이지에 대해 for i in range(N): # 한 명도 도달한 사람이 없을 경우 if (i + 1) not in dic: percentile.append([0., i + 1]) # 여기서 실패한 사용자 수 / (전체 사용자 수 – 이전 단계까지 탈락한 누적 탈락자 수) else: percentile.append([–dic[i + 1] / (len(stages) – cnt), i + 1]) # 누적 탈락자 수를 증가 cnt += dic[i + 1] # 비율로 내림차순 정렬, 같은 비율일 경우 percentile.sort() answer = [x[1] for x in percentile] return answer | cs |