[algorithm] 백준 - 다음 순열
순열을 나열했을 때 주어진 순열 다음 순열을 출력하는 문제이다. 1, 2, 3을 예시로 들어본다면, 다음 순열은 1, 3, 2가 된다. 1, 2, 3, 4를 예시로 들어본다면, 다음 순열은 1, 2, 4, 3이 된다. 1, 2, 4, 3의 다음 순열은 1, 3, 2, 4가 된다. 4, 3, 2, 1의 다음 순열은 없으므로 -1을 출력한다. 다음 순열이 존재할 수 있는 조건은 arr[i - 1] < arr[i]가 존재해야한다. 뒤에서 앞으로 반복문을 수행 후, 이 조건에 만족하는 수를 기준으로 양쪽으로 나눈다. 이후 arr[i - 1]보다 큰 수를 arr[i] 쪽 순열을 뒤에서 앞으로 조회 후 swap한다. 그 후 arr[i] 쪽 순열을 오름차순 sort하면 다음 순열이다. 자세히 살펴보자면, arr[0]..
2020. 10. 28.