[Python 파이썬] 프로그래머스 - 줄 서는 방법

 

2024년 6월 7일

문제 링크 : 프로그래머스 - 줄 서는 방법

프로그래머스

 

 

---

문제 접근

 

n이 주어졌을 때, 1 ~ n 까지 모든 수의 조합을 오름차순 정렬하여, k번째 조합을 찾는 문제이다.

 

n에 대한 모든 경우의 수를 구해 k번째 조합을 구하면 큰일난다.

n의 최대값은 20이며 시간복잡도는 O(n!), 가능한 조합의 수는 20!로 이는 2,432,902,008,176,640,000 ~= 10^19인 아주 큰 수다. 시간복잡도 말도 안된다..

 

이 문제를 해결하기 위해서는 해당 큰 문제를 작은 문제로 쪼갤 수 있는지 접근해보아야 한다.

 

 

n이 4라면, 위와 같이 모든 경우의 수를 오름차순으로 정렬할 수 있을 것이다.

 

여기서 우리는 규칙을 찾을 수 있다.

 

가장 앞 자리수를 1, 2, 3, 4로 고정해본다면, 각각 특정 범위를 내포하는 블록을 가지고 있다는 점이다.

만약 k가 15라면 13 ~ 18 사이에 존재할 것이라고 추측 가능하다.

맨 앞자리 수가 3인 것이 확정되었으니, 그 다음 자리수가 무엇인지 추측해보아야 한다.

그 다음 자리수로 올 수 있는 1, 2, 4 각각 특정 범위를 내포하는 더 작은 블록을 가지고 있고, 이를 통해 대략적인 위치를 알 수 있다.

15번 째 수가 포함되어 있을 블록은 2 번째 자리수가 2일 때임이 확정되었으므로 남은 1, 4로 각각 특정 범위를 내포하는 더 작은 블록으로 나누어본다. 이를 통해 15번째 경우의 수는 [3, 2, 1, 4]임을 알 수 있다.

 

모든 경우를 무작정 계산해 k까지 도달해보는 것이 아닌, 범위를 점점 좁혀가며 대략적인 위치를 계속해서 구해보는 것이다.

 

이를 n이 5이고 k가 34일 때로 가정하면 다음과 같은 전체 흐름도를 그릴 수 있다.

 

 

 

블럭의 범위를 좁혀나갈 때마다 k 값을 계속 수정해준다. 수정된 k값은 현재 블록에서는 몇 번째인지 나타내는 수이다.

 

나머지 로직은 n = 4일 때와 같은 수행 방법을 가지므로 설명은 생략하겠다.

 

---

순서도

 

1. n과 k를 입력받는다.

2. 각 자리수에 들어갈 수 있는 1 ~ n을 순서대로 담을 num_list를 선언 및 초기화한다.
인덱스 번호와 각 인덱스 번호의 요소 값을 동일시키기 위해 0번째 인덱스에 0을 추가해준다.

3. 반복문을 수행하며, 각 반복문 당 블록의 크기를 구한다.
3-1. k가 특정 블록이 내포하는 범위에 포함되면 해당 블록에서 k의 위치를 재연산하여 구한다.
3-2. 현재 블럭의 가장 큰 자리수를 answer에 append하고 자리수에 사용된 수는 num_list에서 삭제한다.

4. answer를 출력한다.

 

 

---

전체 코드

 

'''
n <= 20 자연수
20! = 2,432,902,008,176,640,000 ~= 10**19
=> 브루트포스로 구하면 시간초과

문제 접근
1. 정렬 순서
2. 큰 문제를 부분 문제로 쪼갤 수 있음
'''

def solution(n, k):
    answer = []
    
    block_size = 1

    for i in range(1, n + 1):
        block_size *= i

    # 인덱스 번호 = 자리수 동일시키기 위해 0번째 인덱스는 더미 값
    num_list = [i for i in range(n+1)]
    
    for seq in range(n):
        # 현재 자리수 기준 정렬 시, 블럭 당 사이즈 구하기
        block_size //= (n - seq)

        now_block_start = 1
        now_block_end = block_size

        for i in range(1, n + 1):
            # 현재 블럭 안에 찾는 부분 집합이 존재하면 수행
            if now_block_start <= k <= now_block_end:
                # 현재 블럭의 부분 집합에서 몇 번째 순번을 찾아야 하는지 k 값 수정
                k = k - now_block_start + 1

                # 현재 블럭의 가장 큰 자리수를 answer에 append
                answer.append(num_list[i])

                # 해당 자리수에 사용된 수는 remove
                num_list.remove(num_list[i])
                break

            # 아니라면 다음 블럭 범주를 탐색
            now_block_start += block_size
            now_block_end += block_size

    return answer

if __name__ == "__main__":
    n = 3
    k = 5
    print(solution(n, k))

---

풀이 후기

 

문제에서 규칙을 찾아, 큰 문제를 작은 문제로 쪼갤 수 있는지 확인하는 문제라고 생각한다.