081 순열의 순서

첫번째 코드

 

이 문제는 순열의 문제이고 손으로 많이 풀어본 문제라고 생각이 들었다.

하지만 코드로는 처음 접해봐서 코드는 책을 참고했다.

 

여기서 중요한 것은 소문제1, 2번 문제를 푸는 방법이다.

 

책에서는 아래와 같이 설명한다.

 

소문제1

1. 주어진 값(k)와 현재 자리(n)-1에서 만들 수 있는 경우의 수를 비교한다.

2. 1에서 k가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다.(순열의 순서를 1씩 늘림)

3. k가 더 작아지면 순열에 값을 저장하고 k를 k-(경우의 수 * (cnt-1))로 업데이트 한다.

4. 순열이 완성될 때까지 1~3을 반복하고 완료된 순열을 출력한다.

 

소문제2

1. 현재 자릿수의 숫자를 확인하고 해당 숫자보다 앞 숫자 중 미사용 숫자를 카운트한다.

2. 미사용 숫자 개수 * (현자 자리 -1에서 만들 수 있는 순열의 개수)를 k에 더한다.

3. 모든 자릿수에 관래 1~3을 반복한 후 k값을 출력한다.

---

하지만 해당 글이 이해가 잘 되지 않아 수학 문제를 풀듯이 접근해보았는데, 똑같은 말이었다.

도움이 될지는 모르겠지만 같이 넣어둔다!

 

이런 개념을 바탕으로 아래 코드를 작성하면 된다!

 

import sys
input = sys.stdin.readline

numbers = [0] * 21
sequence = [0] * 21
visited = [False] * 21
n = int(input())
numbers[0] = 1

for i in range(1, n+1):
    numbers[i] = numbers[i-1] * i

check = list(map(int, input().split()))

if check[0] == 1:
    k = check[1]
    for i in range(1, n+1):
        cnt = 1
        for j in range(1, n+1):
            if visited[j]:
                continue
            if k <= cnt * numbers[n-i]:
                k -= (cnt-1) * numbers[n-i]
                sequence[i] = j
                visited[j] = True
                break
            cnt += 1
    for i in range(1, n+1):
        print(sequence[i], end =' ')
else:
    k = 1
    for i in range(1, n+1):
        cnt = 0
        for j in range(1, check[i]):
            if not visited[j]:
                cnt += 1
        k += cnt * numbers[n-i]
        visited[check[i]] = True
    print(k)

 

통과!

수학적인 이해와 코드를 조금 차분히 작성한다면 다음에 작성할 수 있지 않을까? 라는 기대감이 든다!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1722.%E2%80%85%EC%88%9C%EC%97%B4%EC%9D%98%E2%80%85%EC%88%9C%EC%84%9C

programmers/백준/Gold/1722. 순열의 순서 at main · ornni/programmers