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

오늘도 코로나 덕분에 방구석 아싸다...

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

 

오늘은 이 문제를 풀어봤다!

 

문제 설명

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]

 

입출력 예를 보면 알겠지만 굉장히 간단한 문제다!

사전 순으로 줄 서는 방법을 나열하고 거기서 k 번째의 방법을 return 하는 문제!

 

풀이 방법

해당 문제를 보자마자 순열이 생각났는데 문제는 순열의 복잡도는 O(2^n)인가 O(n!)였고 범위가 20이라서 혹시...?라는 마음으로 한번 시도해 봤지만 역시는 역시였다 효율성을 초과했다 ㅎㅎㅎ.....

그래서 다른 방법을 사용했다.  세션을 나눠서 계속 도는 방법을 택했다. 풀이 방법을 말하기가 힘들어 그림을 그렸다.

위에 그림처럼(그림이 개발새발....) 범위를 쪼개서 답이 나올 때까지 구하는 방법을 택했다.

 

왜?

일단 순열은 힘들었고 보통 이런 문제의 경우에는 범위를 계속 쪼개서 푸는 방법이 가장 적합하고 시간 복잡도도 적어서 이런 방법을 택했다.

 

그리고 순열 함수는 시간 복잡도가 너무 크기 때문에 범위가 10 넘어가는 순간 쓰지 않는 게 좋다는 걸 알게 되었다.

 

코드

# import itertools

# def solution(n, k):
#     answer = []
#     for i in range(1,n+1):
#         answer.append(i)
#     nPr = list(itertools.permutations(answer, n))
    
#     return list(nPr[k-1])
# 이 방법은 시간 초과가 난다.
# 정보) 코테에서 순열을 써야하는데 범위가 15 넘어가면 가급적 쓰지 말자...

# 이 문제를 푸는 방법은 세션을 나눠서 푸는 방법이다.
# 예시를 가지고 보면
# 1. 미리 line 리스트에 1~n까지의 값을 넣어놓는다.
# 2. k가 5 일때 5를 (n-1)!로 나누고 그럼 2가 나오고 그럼 두번째 세션을 고르고(두번째 세션은 여기서 말하는 3번째인 3으로 시작하는 세션임.)
# 3. 이제 line 리스트에서 그 세션값을 빼서 answer에 넣는다.
# 4. k 값을 (n-1)!의 나머지로 정한다.
# 5. 반복한다. line의 릴스트에 값이 없어질 때까지.
# 이러면 범위가 좁아지면서 값을 고를 수 있다.
import math

def solution(n, k):
    answer=[]
    line=[]
    for i in range(1,n+1):# 1번
        line.append(i)    
    k=k-1 # 이렇게 하는 이유는 값을 처리할 때 1이 시작이 아니라 0을 시작으로 처리했기때문에 k도 거기에 맞춰 -1해줌
    while len(line)!=0:# 5)
        n-=1
        standard_line=math.factorial(n)
        value=k//standard_line # 나눗셈 2)
        
        answer.append(line.pop(value)) #3)
    
        k=k%standard_line # 4)
        
    return answer

 

 

실행 결과