줄 서는 방법

줄 서는 방법
연습문제
1218명 완료

https://programmers.co.kr/learn/courses/30/lessons/12936

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

전수조사(brute force). 당연히 시간 초과.정답 비교용. 

def solution(n, k):
    from itertools import permutations
    lines = permutations([each for each in range(1, n + 1)])
    for each in range(k - 1):
        lines.__next__()
    return list(lines.__next__())

정확성  테스트
테스트 1 〉	통과 (0.08ms, 10.8MB)
테스트 2 〉	통과 (12.12ms, 10.7MB)
테스트 3 〉	통과 (5.69ms, 10.6MB)
테스트 4 〉	통과 (0.05ms, 10.7MB)
테스트 5 〉	통과 (0.05ms, 10.7MB)
테스트 6 〉	통과 (0.05ms, 10.7MB)
테스트 7 〉	통과 (0.37ms, 10.8MB)
테스트 8 〉	통과 (0.07ms, 10.7MB)
테스트 9 〉	통과 (0.05ms, 10.8MB)
테스트 10 〉	통과 (147.90ms, 10.7MB)
테스트 11 〉	통과 (233.42ms, 10.7MB)
테스트 12 〉	통과 (302.88ms, 10.6MB)
테스트 13 〉	통과 (589.86ms, 10.8MB)
테스트 14 〉	통과 (0.11ms, 10.7MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)

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

 

첫 번째 열은 (n-1)! = 2 만큼 반복됨을 알 수 있다. 
두 번째 열은 (n-1)! = 1 만큼 반복됨을 알 수 있다. 
마지막 열도 (n-1)! = 1 만큼 반복됨을 알 수 있다. 

이는 n이 4일 때도 성립한다. 
첫 열은 (n-1)! = 3! = 3*2*1 = 6 만큼 반복됨.
(순열의 정의, 경우의 수 등을 생각해봐도 쉽게 알 수 있다. )

 

이때 반복되는 행들을 하나의 그룹으로 생각하자. 

위의 예에서 k=5 일 때 ([3, 1, 2]) 1열을 보자. 

k // (n-1)! 해서  
나머지가 없으면 k // (n-1)! 번째 그룹에 속하고 
나머지가 있으면 k // (n-1)! +1 번째 그룹에 속한다. 
(리스트의 인덱스는 0에서 시작하니
리스트에서 찾을 때는 -1 해줘야 한다.) 

이때 나머지는 다음 행 계산할 때 재사용된다. 

 

반복되는 팩토리얼 보다는 동적 계획법을 응용하자. 

 

def solution(n, k):
    answer, numbers, factorial = [], [], [1]
    for i in range(1, n + 1):
        numbers.append(i)
        factorial.append(factorial[i - 1] * i)
    factorial.pop()
    while factorial:
        unit = factorial.pop()
        index = k // unit
        k = k % unit
        answer.append(numbers.pop(index - (1 if k == 0 else 0)))
    return answer

3항 연산자를 이용할 때 연산 우선 순위에 주의~!

정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.6MB)
테스트 3 〉	통과 (0.04ms, 10.7MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.6MB)
테스트 6 〉	통과 (0.04ms, 10.7MB)
테스트 7 〉	통과 (0.04ms, 10.8MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)
테스트 9 〉	통과 (0.05ms, 10.8MB)
테스트 10 〉	통과 (0.05ms, 10.6MB)
테스트 11 〉	통과 (0.05ms, 10.7MB)
테스트 12 〉	통과 (0.04ms, 10.8MB)
테스트 13 〉	통과 (0.05ms, 10.7MB)
테스트 14 〉	통과 (0.04ms, 10.7MB)
효율성  테스트
테스트 1 〉	통과 (0.05ms, 10.7MB)
테스트 2 〉	통과 (0.05ms, 10.6MB)
테스트 3 〉	통과 (0.05ms, 10.7MB)
테스트 4 〉	통과 (0.05ms, 10.7MB)
테스트 5 〉	통과 (0.05ms, 10.7MB)

def solution(n, k):
    answer, numbers, factorial = [], [], [1]
    for i in range(1, n + 1):
        numbers.append(i)
        factorial.append(factorial[i - 1] * i)
    factorial.pop()
    while factorial:
        unit = factorial.pop()
        index, k = divmod(k, unit)
        answer.append(numbers.pop(index - (1 if k == 0 else 0)))
    return answer

작은 숫자를 다룰 때, divmod는 a//b, a%b 보다 느리다.

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.05ms, 10.7MB)
테스트 3 〉	통과 (0.04ms, 10.7MB)
테스트 4 〉	통과 (0.05ms, 10.6MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.04ms, 10.8MB)
테스트 7 〉	통과 (0.05ms, 10.7MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)
테스트 9 〉	통과 (0.04ms, 10.7MB)
테스트 10 〉	통과 (0.05ms, 10.8MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)
테스트 12 〉	통과 (0.04ms, 10.6MB)
테스트 13 〉	통과 (0.05ms, 10.7MB)
테스트 14 〉	통과 (0.05ms, 10.6MB)
효율성  테스트
테스트 1 〉	통과 (0.07ms, 10.7MB)
테스트 2 〉	통과 (0.05ms, 10.6MB)
테스트 3 〉	통과 (0.05ms, 10.7MB)
테스트 4 〉	통과 (0.05ms, 10.7MB)
테스트 5 〉	통과 (0.05ms, 10.7MB)