정렬) 실패율

실패율

<이것이 코딩테스트이다, , 나동빈, 한빛미디어>

첫번째 접근

• 저장한 값을 제외하고 최대값을 다시 구해야할 때 저장한 값을 삭제해버리면 나머지 원소들의 인덱스가 바뀌기때문에 원하는 값을 얻을 수 없다. 원소를 삭제하지 말고 최소값(-1)으로 변경해줘야한다.
• 다음의 코드로 실행했을 때 일부의 테스트 케이스를 통화하지 못했다. 실패도 아니고 시간초과라고 해서 혼란스러웠다.

# 첫번째 접근
def solution(N, stages):

    # 실패율을 저장할 리스트
    failure = []
    # 1부터 N까지 반복하면서 스테이지 도달한 경우 분모를 1 증가, 클리어한 경우 분자를 1 증가시킴
    for i in range(1, N+1):
        deno, nume = 0, 0
        for stage in stages:
            # 도달하고 클리어한 경우, 분모 증가
            if stage >= i:
                deno += 1
            # 도달하기만 하고 클리어하지 못한 경우, 분자 증가
            if stage == i:
                nume += 1
        
        # 실패율 저장
        failure.append(nume/deno)

    # 인덱스를 저장해줄 리스트 생성
    index_list = []

    for i in range(N):
        # 최대값 구해서 해당 인덱스+1을 리스트에 저장
        max_num = max(failure)
        index = failure.index(max_num)
        index_list.append(index+1)
        # 저장한 인덱스의 값은 -1로 변경
        failure[index] = -1

    return index_list

두번째 접근

• 문제는 0/0을 처리하지 못한다는 데에 있었다. 0/0은 division error를 발생시킨다.
• 0/0일 경우 분모를 1로 변경함으로써 실패율을 0으로 만들 수 있다.

# 두번째 접근
def solution(N, stages):

    # 실패율을 저장할 리스트
    failure = []
    # 1부터 N까지 반복하면서 스테이지 도달한 경우 분모를 1 증가, 클리어한 경우 분자를 1 증가시킴
    for i in range(1, N+1):
        deno, nume = 0, 0
        for stage in stages:
            # 도달하고 클리어한 경우, 분모 증가
            if stage >= i:
                deno += 1
            # 도달하기만 하고 클리어하지 못한 경우, 분자 증가
            if stage == i:
                nume += 1
        # 아무도 도달하지 못한 경우 실패율 0이므로 분모를 0에서 1로 증가(0/0은 division error)
        if deno == 0:
            deno = 1
        # 실패율 저장
        failure.append(nume/deno)

    # 인덱스를 저장해줄 리스트 생성
    index_list = []

    for i in range(N):
        # 최대값 구해서 해당 인덱스+1을 리스트에 저장
        max_num = max(failure)
        index = failure.index(max_num)
        index_list.append(index+1)
        # 저장한 인덱스의 값은 -1로 변경
        failure[index] = -1

    return index_list

성공~!🤓🤓🤓