[프로그래머스] 줄 서는 방법

줄 서는 방법

프로그래머스

 

• 풀이
  • 팩토리얼 규칙 활용
    • n명이 있을 때, 첫 번째 자리가 고정되면 나머지 (n-1)!개의 순열이 만들어짐.
    • k번째 순서를 찾을 때 (n-1)! 단위로 몇 번째 그룹인지 계산 가능.
  • 남은 숫자 리스트에서 꺼내기
    • 선택된 숫자는 리스트에서 제거(pop)
    • 다음 자리는 남은 숫자 중에서 다시 그룹 계산
  • k를 0-based 인덱스로 변환
    • 인덱스 계산 편의를 위해 k -= 1
• 시간 복잡도
  • 팩토리얼 계산: O(n)
  • 자리 선택 과정: O(n^2)
    • list.pop()이 O(n)이라서
    • Array List -> 중간 위치(index)에서 pop하면, 그 뒤에 있는 모든 원소를 한 칸씩 앞으로 옮겨야 함.

def solution(n, k):
    # 팩토리얼 값 미리 구해놓기
    factorial = [1] * (n + 1)
    for i in range(1, n + 1):
        factorial[i] = factorial[i - 1] * i

    people = list(range(1, n + 1))
    answer = []
    k -= 1 #인덱스 값으로

    for i in range(n, 0, -1):
        fact = factorial[i - 1]     # (i-1)!
        idx = k // fact             # 몇 번째 그룹인지
        answer.append(people.pop(idx))
        k %= fact

    return answer