- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12936
Lv2 문제다!
(n - 1)!만큼 i번째 수가 각 인덱스에 있는 걸 발견했지만, 이를 어떻게 구현해야할지 몰랐던 문제다.
이번 기회를 통해서 이 부분 공부해야겠다
문제 이해
- permutation으로 구하면 시간이 오래 걸리므로, 다른 방법을 사용해야한다
- 문제를 보면 1부터 n으로 시작하는 배열이 각각 n! // n == (n - 1)! 개씩 있다
- k 를 (n - 1)!로 나눈 몫(k // (n - 1)!)이 정답 배열에 추가되는 수이므로 answer에 추가한다
- temp에서는 해당 수를 사용했으므로 pop해준다
- k를 (n - 1)!로 나눈 나머지, n은 -1 해준다
- 위의 연산을 총 n번 반복한다
- 정답 풀이 :
import math
def solution(n, k):
temp = [x for x in range(1, n + 1)]
answer = []
k -= 1
# n번 반복
for _ in range(n, 0, -1):
max_num = math.factorial(n)
split_num = max_num // n
answer.append(temp[k // split_num])
temp.pop(k//split_num)
k %= split_num
n -= 1
return answer
'코딩테스트 > 기출' 카테고리의 다른 글
[2021 Dev-Matching: 웹 백엔드 개발자(상반기) / 프로그래머스] 77485번 : 행렬 테두리 회전하기 (0) | 2022.10.21 |
---|---|
[2020 카카오 인턴십 / 프로그래머스] 67257번 : 수식 최대화 (다시) (0) | 2022.10.21 |
[2018 KAKAO BLIND RECRUITMENT / 프로그래머스] 17683번 : [3차] 방금 그 곡 (0) | 2022.10.20 |
[월간 코드 챌린지 1 / 프로그래머스] 68936번 : 쿼드압축 후 개수 (1) | 2022.10.11 |
[월간 코드 챌린지1 / 프로그래머스] 68645번 : 삼각 달팽이 (0) | 2022.10.11 |