Programmers / 줄 서는 방법 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 줄 서는 방법 (2단계)

문제 사이트: https://programmers.co.kr/learn/courses/30/lessons/12936

코딩테스트 연습 - 줄 서는 방법

문제 설명

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

---

 

입출력 예

nkresult

3

5

[3,1,2]

---

나의 풀이 - 첫번째 답 (오답)

- itertools 라이브러리 이용

from itertools import permutations
def solution(n, k):
    answer = []
    arr = [i for i in range(1,n+1)]
    for i in permutations(arr):
        answer.append(i)
        
    return answer[k-1]

사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return해야함

 

첫번째 답안은 채점결과 63점으로 나왔다. 

여러번 코드를 줄여가면서 시도했지만... 돌아오는건 시간초과일뿐

 

그 이유는 라이브러리 사용때문에 시간초과가 난 것이다.

 

따라서 우리는 함수를 새로 정의해서 문제를 풀어나가야한다.

 

풀이과정

 

1. 팩토리얼 함수 정의

def factorial(n):
    v = 1
    for i in range(1, n+1):
        v *= i
    return v

2. 1~n 까지의 수를 담은 리스트 정의

def solution(n, k):
    arr = [i for i in range(1,n+1)]

3. solution 함수에 while문으로 해당 arr 리스트 안에서 반복하도록 코드 작성

 

모범답안

def factorial(n):
    v = 1
    for i in range(1, n+1):
        v *= i
    return v #팩토리얼 함수

def solution(n, k):
    answer = []
    arr = [i for i in range(1, n+1)]
    
    while arr:
        temp = factorial(n-1)
        q, r = divmod(k, temp) # 몫과 나머지를 구해줌
        q = q-1 if r == 0 else q
        
        answer.append(arr.pop(q))
        
        n -= 1
        k = r
        
    return answer

 

맨 처음 숫자로 올 수 있는 숫자는 1, 2, 3이다.

그리고 1,2,3일때 뒤에 올 수 있는 경우의수는 2!(=n-1!)이다. 나눗셈을 통해 몫으로 큰 순서를 잡아 나가는 것이다.

k=5를 2!으로 나누어주면 몫이 2, 나머지가 1이다.

몫이 의미하는것은 index 2번째(python은 0부터 시작하니 직관적으로는 3번째) 값의 숫자가 와야한다는 뜻이다.

 

그리고 첫번째 숫자가 결정되었기 때문에 그다음 1,2 뒤에 올수있는 경우는 1!이다. n을 1감소시키는것이다

그리고 k번째는 나머지 r번째이기 때문에 줄여준다.

 

arr값을 다 쓸때까지 while문으로 반복해준다.

 

---

풀이 참고

https://bladejun.tistory.com/112