1256. [Python]사전

1. 문제

 

https://www.acmicpc.net/problem/1256

 

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 조합론

 

3. 파이썬 코드

 

def searching(N, M, K):
    result = []
    total = N + M
    # 총 길이가 0보다 클때까지
    while total > 0:
        # a의 개수가 0보다 큰 경우 만들 수 있는 조합 식 계산
        if N > 0:
            count = comb(N + M - 1, M)
        else:
            count = 0
        # K번 째 수가 위에서 계산산 조합식 count 값보다 작거나 같은 경우 a 로 시작 혹은 끝
        if K <= count:
            result.append('a')
            N -= 1
        # K번 째 수가 조합식 count 보다 큰 경우 z 로 접근됨
        else:
            result.append('z')
            K -= count
            M -= 1
        # 길이 1개 감소
        total -= 1

    return ''.join(result)
# combnation 개수 체크
from math import comb

N, M, K = map(int, input().split())

if K > comb(N + M, M):
    print(-1)
else:
    print(searching(N, M, K))

 

4. 문제를 풀고난 후 생각

 

• 문자열을 가지고 조합론으로 접근하는 방식으로 처음 접근 방식은 문자 전부를 백트래킹을 통한 조합을 생성하는 방식으로 접근을 했다.
• 이러한 방식으로 접근시 시간초과가 발생하기 때문에 수학적으로 접근을 했다.
• N 과 M 으로 만들 수 있는 조합의 개수를 먼저 체크하고 while 문을 통하여 총 만들 수 있는 모든 자리의 개수 만큼 반복문을 진행한다 (N + M)

예시 => 2 2 2

 

•  위와 같은 문자열이 존재하면 만들 수 있는 모든 경우의 수를 구하면 'aazz', 'azaz', 'azza', 'zaaz', 'zaza', 'zzaa' 6개의 문자열이 나오며 이 중 2번 째 는 'azaz' 가 나오게 된다.
• 여기서 K 값이 최대 치인 6을 넘긴 경우 위와 같은 불필요하게 경우의 수를 구하는 경우가 없어야 하므로 그걸 계산해주기 위해 math 를 사용하여 N+M 개 중 M 개로 만들 수 있는 조합의 수를 미리 체크한다. => 왜 M 으로 하는건가? 문자열을 사전순으로 하게 되던 마지막으로 사용되는 문자는 'z' 이기 때문에 M으로 조합의 개수를 체크한다. 'a' 를 기준으로 나머지 문자열 계산식을 구현함
• 함수 내부를 살펴보면 total 은 N+M 으로 초기값을 선언 해줬고, 이후 반복문에서는 N 값이 0 보다 큰 경우 N + M - 1 (이건 a 를 선택했기 때문에) 에서 'z' 로 만들 수 있는 조합의 개수를 구해준다.
• 만약 구하려는 K 값이 남은 조합보다 작거나 같은 경우 'a' 로 만들 수 있기 때문에 리스트에 'a' 를 추가 후 N을 -1 해준다
• 구하려는 값이 조합보다 큰 경우 다음 사전 순서로 넘어가야 하기 때문에 'z'를 추가한 후 K 에 현재 구한 조합론을 빼주고 M 을 1 뺀다.
• 위와 같이 반복문을 진행하면

• 위 그림과 같이 result 에 저장되는 값, N, M , K 값을 보면 만들 수 있는 조합 개수를 체크할 수 있으며 원하는 K 번 째 문자를 찾을 수 있다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 조합론