Algorithm/프로그래머스
[Python] 프로그래머스 Lv2 - 줄 서는 방법
떵호
2022. 7. 2. 16:41
728x90
🔗 문제 링크
코딩테스트 연습 - 줄 서는 방법
n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람
programmers.co.kr
📂 분류
구현 수학
💡 풀이
이 문제는 규칙만 찾는다면 쉽게 해결할 수 있는 문제이다.
접근 방식
- n!를 구한다.
- n! / n , k % (n! / n)를 구한다. 여기서 몫이 0이라면 -1 해준다.
- 2번의 해당하는 요소를 answer에 넣는다. n은 -1 하고, k는 num으로 나눈 나머지를 넣어준다.
- 1, 2, 3번 과정을 n이 0이 될 때까지 반복한다.
💻 코드
from math import factorial
def solution(n, k):
answer = []
number = [i for i in range(1, n + 1)]
while not n == 0:
num = factorial(n) // n
idx = k // num if k % num else k // num - 1
answer.append(number.pop(idx))
n, k = n - 1, k % num
return answer728x90