정렬
데이터를 특정 기준에 따라서 순서대로 나열

• 선택 정렬 : 가장 작은 데이터를 선택
• 삽입 정렬 : 특정한 데이터를 적절한 위치에 삽입
• 퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈. 피벗(기준) 사용(ex. 리스트에서 첫 번째 데이터를 피벗으로 정한다)
• 계수 정렬(count sort) : 특정한 값을 가지는 데이터의 개수를 카운트하는 방법 (모든 범위를 담을 수 있는 크기의 리스트를 선언)
  • 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음
  • 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용

✅ 문제

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨 잇는 배열을 return 하도록 solution 함수를 완성하세요.

입력 예시1

5
2, 1, 2, 6, 2, 4, 3, 3

출력 예시1

[3, 4, 2, 1, 5]

입력 예시2

4
4 4 4 4 4

출력 예시2

[4, 1, 2, 3]

💻 코드

def solution(N, stages):
    stage_count = [0] * (N+1)
    for stage in stages:
        stage_count[stage-1] += 1

    fail_rate = [0] * N
    front_user = 0
    fail_rate[0] = (stage_count[0]/len(stages),1)

    for i in range(1, len(stage_count)-1):
        front_user += stage_count[i-1]
        
        # 사용자가 높은 스테이지까지 도달하지 못한 경우 스테이지에 도달한 플레이어의 수가 0이므로 실패율을 0으로 정해준다. 
        if len(stages) - front_user != 0:
            fail_rate[i] = (stage_count[i]/(len(stages) - front_user), i+1)
        else:
           fail_rate[i] = (0, i+1)

    result = sorted(fail_rate[:N],key= lambda x: x[0], reverse=True)
    answer = [i[1] for i in result]

    return answer

설계

실패율과 스테이지를 한 번에 저장하기 위해서 튜플로 실패율과 스테이지를 리스트에 저장하였다.
front_user는 현재 스테이지까지 도달하지 못한 사용자의 수를 나타낸다.

➕ 다른 풀이

def solution(N, stages):
    answer = []
    length = len(stages)

    for i in range(1, N+1):
        count = stages.count(i)

        if length == 0:
            fail = 0
        else:
            fail = count / length
        
        answer.append((i, fail))
        length -= count
    
    anwser = sorted(answer, key= lambda t: t[1], reversed=True)

    answer = [i[0] for i in answer]
    return answer

• 나는 stages를 for문으로 stage에 머물고 있는 사용자의 수를 일일이 계산했는데 이 풀이에서는 count() 함수로 쉽게 구하였다.
• 나는 실패율의 리스트의 크기를 미리 구했는데, 여기서는 리스트에 실패율을 추가하는 식으로 구하였다. 그래서 for문의 조건식을 스테이지 숫자만큼으로 정해주어 조건식이 더 깔끔해졌다.

📝 정리

실패율과 스테이지를 함께 저장하기 위해서 튜플을 사용했는데, 다른 풀이를 보니 딕셔너리를 사용하기도 했다.
다른 풀이를 보면서 파이썬 문법이 어떻게 사용될 수 있는지 배워야 겠다.

딕셔너리
{Key1: Value1, Key2: Value2, ...}

딕셔너리 쌍 추가
a[1] = 'a'
{1: 'a'}