•
•
문제 설명 : 리스트가 제공될 때, 사전식 배열을 사용할 경우 다음 순열은 어떤게 나와야할지 처리한다.
•
풀이 방법
◦
우선 사전식 정렬에 대해 이해가 필요하다.
▪
위 블로그가 자세하게 설명하였으니 참고하면 된다.
◦
간단하게 코드를 설명하면 아래와 같다.
▪
가장 마지막 내림차순이 시작되는 index (start 변수)
▪
내림차순 직전 index 값보다 크지만, 내림차순 범위 중에서는 가장 작은 값
•
EX) [1, 4, 3, 2] 의 경우 2가 된다.
◦
마지막 내림차순 직전 index → 0 / value 1
◦
마지막 내림차순 중 가장 작은 값 → index → 3 / value 2
•
EX) [1, 7, 6, 4, 5, 3, 2] 의 경우 2가 된다.
◦
마지막 내림차순 직전 index → 3 / value 4
◦
마지막 내림차순 중 가장 작은 값 → index → 4 / value 5
▪
[1, 4, 3, 2] 와 같이 이미 첫번째 1 이후 모두 내림차순이라면, 0인덱스의 1을 2로 변경해줘야한다.
•
1과 2를 변경하여, 다음 사전 순서로 변경한다.
▪
[2, 4, 3, 1] 과 같이 변경되었다면, 기존 내림차순 범위 요소들을 오름차순으로 변경해야한다.
•
즉, 이 말은 오름차순 → 내림차순으로 점차 변한다
•
키가 바뀌면, 내림차순 범위를 다시 오름차순으로 변경하고 반복하는 것이다.
◦
너무 오래동안 못풀면서, 솔루션을 보고 마무리할까 고민했지만 구현을 어떻게 해야할지는 명확하게 찾은 상황이기 때문에 예외 처리를 하는데 많은 시간을 쓴 것 같다.
▪
구현 방법조차 고민되거나 너무 장황한 상태라면, 솔루션을 보는게 맞는 것 같다.
◦
종이로 규칙을 찾으면서 겨우겨우 풀었는데, 다른 솔루션보다도 짧고 간결한 코드로 풀은 것 같아 시간은 오래 걸렸지만 기분은 좋았다.
•
시간복잡도 : → 오름차순으로 정렬되는 내림차순 범위의 길이를 M으로 지정
•
성공 코드
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def asc_for_desc(start):
for i in range((len(nums) - start + 1) // 2):
nums[start + i], nums[~i] = nums[~i], nums[start + i]
start, min_index = 0, 0
for i in range(len(nums) - 1):
# 새로운 내림차순이라면 갱신
if nums[i] < nums[i + 1]:
start = i + 1
# 내림차순 직전 값보다 크다면 갱신
# 내림 차순이기 때문에, 자연스럽게 계속 작아지는 값이 설정
if start > 0 and nums[start - 1] < nums[i + 1]:
min_index = i + 1
# 주어진 리스트 전체가 내림차순이 아닐경우
# EX) [1, 7, 6, 4, 5, 3, 2] -> [1, 7, 6, 5, 4, 3, 2] -> [1, 7, 6, 5, 2, 3, 4]
# 위 3가지 순서 중 2번째로 만들기 위한 과정
if start > 0:
nums[min_index], nums[start - 1] = nums[start - 1], nums[min_index]
# 위 3가지 순서 중 마지막 형태로 만들기 위한 과정
# 내림차순 범위의 값들을 오름차순으로 변경해준다.
asc_for_desc(start)
Python
복사