2019 KAKAO BLIND_실패율

superyodi·2020년 9월 22일
0

Problem Solving

목록 보기
11/16

문제

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

풀이 과정

Wrong Access

문제는 실패율을 정렬한 값을 반환할 것을 요구한다.
실패율은 다음과 같이 정의한다.

실패율:
스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

그래서

  • now_s = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수
  • try_s = 스테이지에 도달한 플레이어 수

이렇게 나타내었다.

try_s를 보니까 try_s[num] = try[num-1] - now[num-1]인 규칙을 찾았고 코드를 짰다.


def solution(N, stages):
    answer = []
    
    # try stage와 now stage
    try_s = [0 for _ in range(N+2)]
    now_s = [0 for _ in range(N+2)]

    # clear_s는 
    '''
    1: 1
    2: 3
    3: 2
    4: 1
    5: 0
    6: 1
    
    '''

    '''
    p_num = len(stages)
    # 이전 now_s의 사람들의 합 
    try_num = p_num - now_s[:num]
    1: 8 - 0
    2: 8 - now[1] = 7
    3: 8 - now[1] - now[2] = 4
    4: 8 - now[1] ... - now[3] = 4 - 2 = 2
    5: try[num-1] - now[num-1] = 2 - 1 = 1

    '''

    for num in stages:
        now_s[num] += 1
    
    accum_per = len(stages)
    for num in range(1, N+1):
        if num == 1:
            try_s[num] = accum_per
            continue
        try_s[num] = try_s[num-1] - now_s[num-1]
        
    fail_s = []
    for num in range(1, N+1):
        fail_s.append([num, now_s[num] / try_s[num]])
    
    fail_list = sorted(fail_s, key=lambda x: (-x[1], x[0]))
    
    for i, j in fail_list:
        answer.append(i)
    print(answer)
        
    # print("now_s: ", now_s)
    # print("try_s: ", try_s)
    # print("fail_list: ", fail_list)
    
    return answer

하지만, 이렇게 했더니 정확도 70프로, 70프로는 통과하고 30프로에선 런타임 에러가 났다.
비록 더럽게 짰지만 O(N)일텐데 런타임 에러가 난 것이 이상해서 몇개의 TC를 추가했더니 아뿔싸

fail_s.append([num, now_s[num] / try_s[num]])에서 try_s[num]이 0이라서 division by zero에러가 나는 경우를 신경쓰지 못했다.

TC가 위와 같을떄 오류가 난다.

그래서 try - except로 에러처리하였다.

Correct Access


def solution(N, stages):
    answer = []
    
    # try stage와 now stage
    try_s = [0 for _ in range(N+2)]
    now_s = [0 for _ in range(N+2)]

    for num in stages:
        now_s[num] += 1
    
    fail_s = []
    for num in range(1, N+1):
        if num == 1:
            try_s[num] = len(stages)
            fail_s.append([num, now_s[num] / try_s[num]])
            continue
        try_s[num] = try_s[num-1] - now_s[num-1]
        
        try:
            fail_s.append([num, now_s[num] / try_s[num]])
        except:
            fail_s.append([num, 0])
        
    
    fail_list = sorted(fail_s, key=lambda x: (-x[1], x[0]))

        
    answer = list(zip(*fail_list))[0]
    print(answer)
    
    return answer

새로 배운 개념

Zip

answer = list(zip(*fail_list))[0]
2차원 리스트의 첫번째 요소들만 골라 list를 만들고 싶을때,
아래와 같은 방법들이 있는데 그 중 zip을 이용했다.

출처: https://emilkwak.github.io/python-2d-list-certain-column

Sort() by lambda key

fail_list = sorted(fail_s, key=lambda x: (-x[1], x[0]))

문제에서 요구하는

  • 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열
  • 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.

위의 두 조건을 만족하도록 sort하려면 key가 두 개 필요했다.
이중 리스트라면 처음은 두번째 요소를 기준으로 내림차순으로 정렬하고, 같은 값이 있으면 첫번째 요소를 기준으로 오름차순으로 정렬해야 했다.

그래서 lambda를 이용해서 sort할 key를 커스텀했고, key는 그리고 위의 두 조건을 담은 튜플로 하였다.

참고: https://dailyheumsi.tistory.com/67

0개의 댓글