> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/brute-force/next-permutation.md).

# Next Permutation

문제 복기

**알고리즘 생각**

1. 사전순으로 증가하는 다음 순열을 구할 때, 다음으로 증가할 x번째 숫자를 찾아야한다.\
   ex)12345 의 다음 순열 : 12354 => 끝에서부터 A\[i-1]\<A\[i]를 만족하는 i를 찾는다. (다음으로 할 인덱스 x = i-1)\
   뒤에서부터 **A\[i-1]\<A\[i]를 만족하는 i** => **i\~n-1까지는 모드 내림차순**이라는 의미! 이\
   후에 나오겠지만, 아래2번 swap을하고, i-(n-1)사이의 수를 오름차순으로 정렬해준다. 수열의 가장 첫번째는 오름차순이고 가장 마지막은 내림차순이기 때문이다.&#x20;
2. i-1번째 수가 다음으로 증가해야하는 수이다. i-1번째 수보다 큰 수를 찾는다.\
   사전순으로 증가하는 순열을 찾는 것이기 때문에 i\~n-1 중에서 큰 수를 찾아야한다.(뒤에서부터 찾는다.)
3. i-1보다 큰 수와 i-1번째 수의 위치를 바꾼다.(수열을 증가시키는 의미)
4. i\<j 라면 i\~n-1 사이의 수를 재정렬시켜 오름차순(첫 수열)로 만들어준다.\
   만약에 i-1보다 큰수를 찾은 인덱스 j가 i와 같다면 종료(또는 위의 연산 불필요)하다.<br>