[프로그래머스/Python] LV3. 줄 서는 방법 (+13)

프로그래머스 코딩테스트 연습 - LV3. 줄 서는 방법

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! 이하의 자연수 입니다.

 

입출력 예시

n	k	result
3	5	[3, 1, 2]

 

풀이 방법

❌ 효율성 실패 : permutation 이용

from itertools import permutations as pm

def solution(n, k):
    a = list(range(1, n+1))
    for i, x in enumerate(pm(a)):
        if i == k-1:
            return list(x)

• 정확성 테스트는 19개 모두 2ms 이내로 통과되지만 효율성 테스트는 3개 모두 실패 (시간 초과)

 

✨ 성공 : 맨 앞부터 채워나가며 k 값 줄이기

import math

def solution(n, k):
    answer = []
    a = list(range(1, n+1))
    
    while k > 1:
        fac = math.factorial(len(a)-1)
        answer.append(a.pop((k-1)//fac))
        k = k - (fac * ((k-1) // fac))
    return answer + a

• 남은 숫자 개수 -1의 팩토리얼을 단위로 끊어서 k를 줄여나가며 맨 앞부터 채워나가면 됨 (아래 표로 이해가 안 된다면 n을 4로 해서 그려보기!)
• while 문 안의 (k-1)이 중요함

• K	(k-1) // fac	출력
  1~2	0	1	2	3
  		1	3	2
  3~4	1	2	1	3
  		2	3	1
  5~6	2	3	1	2
  		3	2	1

 

느낀 점

문제를 보자마자 엥? 그냥 permutations 쓰면 되는데 이게 왜 LV3? 싶었는데 역시나 효율성 테스트에서 걸렸다.

역시 알고리즘을 짤 수 밖에... 처음에 생각없이 while문 안의 (k-1)을 k로 넣었다가 시간 날렸다.

정말 철처하게 시키는 대로만 해서 좋으면서도 빡친다. 융통성 있는 컴퓨터 ㄴㅐㄴㅘ...

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges