[백준] 10972 다음 순열 파이썬 python

문제링크

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

10972번: 다음 순열

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
a = list(map(int, input().split()))
for i in range(n-1, 0, -1):
    if a[i-1]<a[i]:
        target = i-1
        break
else:
    print(-1)
    sys.exit()
 
for i in range(n-1, 0, -1):
    if a[target]<a[i]:
        a[target],a[i] = a[i],a[target]
        a = a[:target + 1] + sorted(a[target + 1:])
        print(*a)
        break
 

 

POINT

- 순열 : 브루트포스 접근

- 풀이방법 : next permutation 알고리즘

 

예를 들어, [1,3,5,4,2] 의 다음 순열을 찾고자 한다.  

Step1.

 더 큰 순열을 만들어야하기에 작은 수가 앞에 배치된 게 있는지 확인해야한다. '5,4,2'는 내림차순으로 배치되어있으니 5,4,2의 조합으로는 더이상 큰 수를 만들 수 없기에 건드릴 필요가 없다고 판단된다. 3<5이므로 Target은 숫자 3!! (==>코드 구현상에서는 Target = 3의 index 1) 

Step2.

 3 이후로는 내림차순으로 배치되어있는것이기 때문에 '5,4,2'를 뒤에서 부터 접근해서 3과 비교해본다. 3보다 더 큰 수가 앞으로 튀어나올 자격이 있다. 3>2이므로 넘어가고, 3<4이기 때문에 3과 4의 자리를 바꿔서 4를 앞으로 보낸다.

여기까지하면, [1,3,5,4,2] -> [1,4,5,3,2]가 된다.

 

Step3.

자 이제, [1,4]로 시작하는 순열이 시작된 것이기 떄문에 그 뒤는 '5,3,2'로 만들 수 있는 제일 작은 순열을 갖추어야한다. 따라서 sorted를 통해 오름차순 배열을 한다. 

[1,4] + sorted[5,3,2] =>> [1,4,2,3,5] 완성!!!!

 

  

파이썬 Asterisk * 용도

1) 곱셈, 거듭제곱

2) 가변 인자

     *args(positional arguments), **kargs(keyword arguments) 

3) 리스트, 튜플 확장

     [1]*3 = [1,1,1] 

4) Unpacking   ==> 코드에서 다음 기능 사용!

     a=[1,2,3] *a = 1 2 3

5) 가변 할당

    a = [1,2,3,4,5]     b, *c, d = a    (--> b = 1, c =[2,3,4], d = 5) 

https://hwiyong.tistory.com/193

파이썬 asterisk(*) 사용 용도