이 포스팅은 프로그래머스 시리즈 28 편 중 23 번째 글 입니다.

  • Part 1 - 01: 다리를 지나는 트럭
  • Part 2 - 02: 멀정한 사각형
  • Part 3 - 03: 더 맵게
  • Part 4 - 04: 메뉴 리뉴얼
  • Part 5 - 05: 전화번호 목록
  • Part 6 - 06: 가장 큰 수
  • Part 7 - 07: 예상 대진표
  • Part 8 - 08: 다단계 칫솔 판매
  • Part 9 - 09: 불량 사용자
  • Part 10 - 10: 베스트 앨범
  • Part 11 - 11: 합승 택시 요금
  • Part 12 - 12: 스타 수열
  • Part 13 - 13: 위장
  • Part 14 - 14: 주식 가격
  • Part 15 - 15: 디스크 컨트롤러
  • Part 16 - 16: N으로 표현
  • Part 17 - 17: 전화번호 목록
  • Part 18 - 18: 단어 변환
  • Part 19 - 19: 여행 경로
  • Part 20 - 20: 프린터
  • Part 21 - 21: 후보키
  • Part 22 - 22: 삼각 달팽이
  • Part 23 - This Post
  • Part 24 - 24: 입국심사
  • Part 25 - 26: 기둥과 보 설치
  • Part 26 - 27: 광고 삽입
  • Part 27 - 28: 퍼즐 조각 채우기
  • Part 28 - 29: 상호 평가
▼ 목록 보기

목차

▼ 내리기

풀이

일단, 200,000이라서 n^2은 안된다. 그러면 한번에 가야하는데, 이 때, 잘 살펴보면, 해당 스테이지에서의 실패율은 stage잔존 수/stage 통과수로 정의된다. 통과수의 경우 4스테이지에 있는 경우 이전 1, 2, 3스테이지에 있을 때 모두 카운트가 되기 때문에 이부분을 잘 살펴야 한다.

즉, 현재 스테이지에 있는 수 / 현재 스테이지보다 큰 스테이지에 있는 사람수 가 실패율이다. 여기까지 도달했다면, 어떻게 하면 큰 스테이지 수를 쉽게 구하는지 생각해볼 수 있는데, 정렬을 하게 되면 포인터를 쭉 이동하면서 한번에 풀이가 가능하다.

맞다. 0인경우 처리잘해주어야 한다.

Code

def solution(N, stages):
    success = dict([[x, 0] for x in range(1,N+2)])
    tries = dict([[x, 0] for x in range(1,N+2)])
    
    stages.sort()
    i = 0
    stage_num = 1    
    while i < len(stages):
        if stages[i] == stage_num:
            success[stage_num] += 1
            i += 1
        else:
            tries[stage_num] = len(stages)-i
            stage_num += 1
    
    fail_ratio = []
    for num in range(1, N+1):
        if success[num]+tries[num] == 0:
            fail_ratio.append([num, 0])
        else:
            fail_ratio.append([num, success[num]/(success[num]+tries[num])])
    
    fail_ratio = sorted(fail_ratio, key=lambda x: (x[1], -x[0]), reverse=True)
    
    return [x[0] for x in fail_ratio]

Reference