[Level 1] 실패율

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

코딩테스트 연습 - 실패율

---

첫 번째 접근

각 stage마다 해당 stage에 있는 사람의 수를 분자, stage 이상인 사람을 분모로 하여 해당 값을 stage 번호와 함께 리스트에 추가한다. 이후 리스트에서 실패율을 기준으로 내림차순 정렬하고 최종적으로 첫 번째 값부터 탐색해서 stage를 출력하도록 한다.

 

첫 번째 구현

- stage를 1부터 N까지 진행하여

- stages 리스트를 탐색하여 stage와 같을 때는 x를 증가, stage 이상일 때는 y를 증가한다.

- 이후 (x/y, stage)를 튜플 형태로 리스트에 추가하고

- 해당 리스트를 첫 번째 값을 기준으로 내림차순 정렬한다.

- 최종적으로 리스트에서 값을 꺼내서 stage만 result에 담아서 반환한다.

def solution(N, stages):
    answer = []
    for stage in range(1, N+1):
        x = 0
        y = 0
        for number in stages:
            if number == stage:
                x += 1
            if number >= stage:
                y += 1
        if x == 0 or y == 0:
            answer.append((0, stage))
        else:
            answer.append((x/y, stage))
    answer = sorted(answer, key=lambda x: -x[0])
    result = []
    for x, y in answer:
        result.append(y)
    return result

---

두 번째 접근

누적합을 활용하였다. 먼저 각 스테이지마다 도달한 사람의 수를 counter리스트에 저장한다. 그리고 acc 리스트에 현재 스테이지 이상으로 클리한 사람의 수를 누적합으로 계산하여 저장한다.

이를 위해서는 0번 인덱스부터가 아닌 가장 끝의 인덱스부터 탐색을 진행하여 계산해야 한다. 즉 [1, 3, 0, 2]가 있을 때 3번 인덱스부터 0번 인덱스까지 탐색을 하여 해당 인덱스의 counter 값과 +1한 인덱스의 acc 값을 더하도록 한다.

 

두 번째 구현

- counter 리스트는 최대 N+1까지의 값이 있기 때문에 N+2만큼 생성하였고

- acc 리스트는 최대 N+1까지 있기 때문에 N+2부터 진행되도록 하기위해 N+3만큼 생성하였다.

- 먼저 stages를 탐색하여 counter 리스트에 각 stage까지 도달한 사람의 수를 측정하고

- 이를 활용하여 acc 리스트에 누적 합의 결과를 저장한다.

- 이제 counter와 acc를 활용하여 counter[i]/acc[i]로 실패율을 측정하도록한다.

- 이후부터는 위의 코드와 동일한 로직이다.

def solution(N, stages):
    answer = []
    counter = [0 for _ in range(N+2)]
    acc = [0 for _ in range(N+3)]
    
    for stage in stages:
        counter[stage] += 1
    
    for i in range(N+1, 0, -1):
        acc[i] = counter[i] + acc[i+1]
    
    temp_list = []
    for i in range(1, N+1):
        if counter[i] == 0 or acc[i] == 0:
            temp_list.append((0, i))
        else:
            temp_list.append((counter[i] / acc[i], i))
    temp_list = sorted(temp_list, key=lambda x: -x[0])
    for a, b in temp_list:
        answer.append(b)
    return answer