Next Permutation
문제 복기
알고리즘 생각
사전순으로 증가하는 다음 순열을 구할 때, 다음으로 증가할 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)사이의 수를 오름차순으로 정렬해준다. 수열의 가장 첫번째는 오름차순이고 가장 마지막은 내림차순이기 때문이다.
i-1번째 수가 다음으로 증가해야하는 수이다. i-1번째 수보다 큰 수를 찾는다. 사전순으로 증가하는 순열을 찾는 것이기 때문에 i~n-1 중에서 큰 수를 찾아야한다.(뒤에서부터 찾는다.)
i-1보다 큰 수와 i-1번째 수의 위치를 바꾼다.(수열을 증가시키는 의미)
i<j 라면 i~n-1 사이의 수를 재정렬시켜 오름차순(첫 수열)로 만들어준다. 만약에 i-1보다 큰수를 찾은 인덱스 j가 i와 같다면 종료(또는 위의 연산 불필요)하다.
Last updated