Baekjoon10972 - 다음 순열(Python)

백준 사이트 10972 - 다음 순열 문제입니다.

이 글을 보시기 전에 문제를 풀기 위해 충분한 생각을 하셨나요? 답을 안 보고 푸는게 최대한 고민하는게 가장 중요하다고 생각합니다.!!

☑️ 1. 문제

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

---

☑️ 2. Input , Output

자세한건 링크 참조..

---

☑️ 3. 분류 및 난이도

코딩테스트 준비-기초 : 브루트포스 - 순열 문제입니다.

---

☑️ 4. 생각한 것들

• 처음에는 런타임에러가 계속 뜨길래 의아했습니다. 나눗셈도 없었는데 말이죠.
• 찾아보니 순열을 찾는 재귀가 너무 깊어서 나느거일수도 있다고 합니다.
• 그래서 다음 순열을 직접 구해줘야하는데, 그건 구글에 검색하여 알고리즘을 학습하였습니다.

https://blogshine.tistory.com/122를 참고하였습니다.

---

5. code

def solution(origin, size):
    i = size - 1
    while i > 0 and origin[i - 1] >= origin[i]:
        i -= 1
    if i <= 0:
        return

    j = size - 1
    while origin[j] <= origin[i - 1]:
        j -= 1
    origin[i - 1], origin[j] = origin[j], origin[i - 1]

    j = size - 1
    while (i < j):
        origin[i], origin[j] = origin[j], origin[i]
        i += 1
        j -= 1
    print(' '.join(map(str, origin)))


n = int(input())
input_str = list(map(int, input().split()))
permu_list = [_x for _x in range(1, n + 1)]

if list(input_str)[::-1] == permu_list:
    print(-1)
else:
    size = len(permu_list)
    solution(input_str, size)

---

6. 후기

• 사실 처음에 역 배열인 경우를 걸러주기 때문에 solution안의 if i<=0구문이 없어도 됩니다. 다른데서도 쓸 거 같아서 코드상에서는 냅두었습니다.

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.