next_permutation : 3단계 최적화를 하면서 분석해 보자.

 코딩 테스트에서 next_permutation의 사용 빈도는 상당히 높을 겁니다. 특히 역량 테스트라고 불리는 것에서는요. 구현이 들어가면 대략 50% 정도는 조합, 순열 등에서 나오는데요. 그 때, 이전 순열이라던지 다음 순열을 구하기 위해서 쓰는 함수가 저 함수입니다. 이전 순열은 데이터를 조금 변형을 하면 구할 수 있고요.

 

 그러면 이 함수가 어떻게 구현이 되어 있을까요? 만약에 레퍼런스 없이 구현하라고 하면 어떻게 해야 할까요?

 

 

---

 단계별로 이해해 봅시다. 사실 이 함수의 복잡도는 O(n)입니다. 왜 그렇게 나올 수가 있는 것인지, 상대적으로 비효율적인 구현 방법으로 먼저 구현해 보고 이야기 하도록 하겠습니다. O(n^2)의 핵심 접근은, 결정 함수입니다. 이게 무슨 어려운 것이냐라고 생각하실 수도 있겠습니다만. 큰 그림을 먼저 그려봅시다.

 

 

 예를 들어 [2, 1, 3, 5, 4]의 다음 순열을 구한다고 해 봅시다. 그러면 2xxxx가 나올 수 있을까요? 를 먼저 생각해 봅시다. 2xxxx 중에, 사전순으로 제일 뒤인 것은 2 5 4 3 1입니다. 이것은 2 1 3 5 4보다 명확하게 큰 것이 자명합니다. 따라서, 맨 앞의 숫자는 2입니다.

 

 

 그러면, 다음 순열이 21xxx꼴일까요? 21xxx꼴 중에서 사전 순으로 제일 뒤에 있는 것은 2 1 5 4 3입니다. 2 1 3 5 4는 이것보다 앞서기 때문에 21xxx꼴이 나옵니다.

 

 

 그러면 다음 순열이 213xx꼴인가요? 213xx꼴 중, 사전순으로 가장 뒤에 있는 것은 2 1 3 5 4입니다. 그런데, 보시면 아시겠지만, 지금 현재 순열이 2 1 3 5 4입니다. 따라서 213xx꼴은 아님을 알 수 있어요.

 

 

---

 그러면 이 때, next perm은 어떻게 구해야 할까요? 213xx꼴이 아니라면, 213보다 큰 패턴인 21?을 구해야 합니다.

 

 

 그러면, 우리는 이미 답이 확정된 보라색 부분과, 재정렬을 해야 하는 초록색 부분으로 나눌 수 있는데요. 213보다 큰 패턴인 21?를 초록색에서 찾아 봅시다. 그러면 ?는 4 아니면 5가 올 수 있어요. 즉, 214xx나, 아니면 215xx가 올 수 있는데요. 이 중, 우리는 214xx 패턴을 택합니다.

 

 

 그러면 214xx 패턴을 만들어야 하니까, 주황색으로 칠한 두 부분을 swap 해야 할 거에요.

 

 

 그러면 2 1 3 5 4보다는, 214xx가, 사전순으로 더 뒤에 있는 건 확실한 셈입니다. 그러면 초록색 부분은 어떻게 하면 좋을까요? 정렬하면 됩니다.

 

 

 따라서, 2 1 3 5 4의 next_perm은 2 1 4 3 5가 됩니다. 제가 찾았던 이러한 방식은 백준 1020번 문제인 디지털 카운터와, 1112번 진법 변환에서도 상당히 유용하게 쓰이는 결정 방법이므로 알아두시면 도움이 될 듯 싶습니다.

 

 

---

 또 다른 예제를 봅시다.

 

 

 5, 1, 5, 3, 2, 2의 다음 순열은 어떻게 구하면 좋을까요? 5xxxxx꼴에서 사전 순으로 가장 뒤에 있는 것은 5 5 3 2 2 1입니다. 5 1 5 3 2 2는, 이것보다는 앞선 게 자명하기 때문에 답이 5xxxxx꼴일 겁니다.

 

 

 그러면 51xxxx꼴일까요? 51xxxx꼴 중에서 제일 뒤에 있는 것은 5 1 5 3 2 2입니다. 5 1 5 3 2 2는 이것보다 앞서지는 않습니다. 따라서 51xxxx꼴이 아닙니다. 그러면 5?xxxx꼴일 건데, ?는 1보다는 큰 어떠한 것일 겁니다.

 

 

 그러면 이것을 초록색 부분 중에서 찾아봅시다. 후보해가 2, 3, 5가 있는데 51꼴보다 5?가 뒤에 있으려면 ?는 1보다는 커야 합니다. 그러면 ?에는 2, 3, 5가 들어갈 수 있는데, 이 중 가장 작은 것은 2입니다.

 

 

 그러면 1과 2를 서로 바꿉니다.

 

 

 다음에 52xxxx꼴은 5 1 5 3 2 2보다 뒤에 있는 것이 자명합니다. 따라서 초록색 부분을 오름차순으로 정렬합니다. 그러면, 5 2 1 2 3 5가 됩니다.

 

 

 따라서 5 1 5 3 2 2 다음에 오는 것은, 5 2 1 2 3 5입니다. 당연하게도, 내림차순으로 정렬이 된 순열 다음에 오는 것은 없으니까, 이 때에는 적절히 처리를 잘 하시면 좋겠네요.

 

 

---

 문제는, 이런 식으로 앞에서부터 쭉 본다면, 5?????꼴일 때 ?????을 나머지 수들을 내림차순으로 넣은 것과 compare 하고, 다음에 51????꼴일 때 ????를 나머지 수들을 내림차순으로 넣은 것과 compare 하고. 이런 식으로 쭉 진행을 한다면, n^2가 걸립니다. n의 값이 5만만 되어도 시간초과가 날 게 분명할 듯 싶은데요. 이 부분을 어떻게 개선할 수 있을까요? 문제의 부분을 노란색으로 표시해 봅시다.

 

 

 2번째 예제에서 문제의 위치를 노란색으로 표시해 보았습니다. 이 노란색으로 칠해진 값 1과 2를 바꾸었습니다.

 

 

 1번째 예제에서는 노란색으로 칠해진 부분 3과 4를 바꾸었습니다. 이 둘의 공통점이 무엇일까요? 바로 뒤에서부터 보았을 때, arr[i-1] < arr[i]인 최초의 지점이였다는 겁니다. 그러면 노란색으로 표시한 위치를 기준으로 왼쪽 것은 보라색, 오른쪽은 연두색으로 나눌 수 있을 건데요.

 

 연두색 부분 중에서 노란색으로 칠한 부분보다 큰 것들 중에, 가장 작은 값과 바꾸었습니다. 이를 코드로 구현해 보면 다음과 같습니다.

 

 

 먼저 우리는 뒤에서부터 보았을 때, arr[i-1] < arr[i]인 최초의 지점을 뽑았습니다. 이 때 lo값은 노란색을 가리키고 있을 겁니다. 그러면 lo+1번부터 n-1번까지는 초록색 부분에 해당할 겁니다.

 

 

 32번째 줄의 for문은 초록색으로 칠한 것 중에서 arr[lo], 그러니까 노란색 값보다는 크면서, 기존에 알려졌던 최솟값보다 작으면 mmn의 값을 업데이트 하였는데요. 이 때 lo2의 값도 같이 업데이트 해 줍니다. 그러면 for loop를 다 돌고 난 후에는 lo에 있는 원소와 lo2에 있는 원소를 맞바꾸면 될 거에요.

 

 그리고, lo+1번째부터 n-1번째 원소까지 sort 함수를 호출해서 정렬하면 됩니다. 그러면 최악의 경우 O(nlogn) 정도의 복잡도를 지니게 됩니다.

 

 

---

 그런데 여기에서도 불필요한 오버헤드가 있다는 거 눈치 채셨나요? 내림차순으로 정렬된 어떤 데이터를 오름차순으로 정렬하기 위해서는 sort를 호출해도 됩니다. 하지만, 거꾸로 출력해도 됩니다. 왜냐하면 앞에서 보았을 때 내림차순인 것은, 뒤에서부터 보았을 때 오름차순이기 때문입니다.

 

 

 그러면 이 경우에, 1과 어떠한 친구를 바꾸었을 때 초록색 부분이 내림차순이 유지되도록 바꿔봅시다. 그리고, 노란색 부분은 1보다 큰 원소이면서 가장 작은 것을 가지고 오면 좋겠습니다. 이건 어떻게 O(n)만에 찾을까요? 간단합니다. 뒤에서부터 보면 됩니다.

 

 초록색 부분은 이미 내림차순으로 정렬이 되어 있었기 때문에, 초록색 부분에 속하는 인덱스 a, b가 있고, a<b인 경우에는 arr[a] >= arr[b]인 것이 자명하기 때문입니다.

 

 

 그러면 뒤에서부터 보았을 때, arr[5]의 값이 2이고, 위치 5는 뒤에서 부터 보았을 때, 1보다 큰 최초의 위치입니다. 그러면 이 위치에 있는 값과 arr[lo]에 있는 값을 서로 맞바꿉니다.

 

 

 그러면 초록색 부분이 내림차순으로 정렬이 되어 있습니다. 이것을 오름차순으로 바꾸기 위해서는 포인터를 2개를 둡니다. s와 e. 이 때 s는 lo+1째를, e는 n-1번째 원소를 가리킵니다.

 

 

 다음에 s<e를 만족하면 arr[s]와 arr[e]를 맞바꾸고 s는 1칸 증가, e는 1칸 감소시키면 됩니다. 먼저 s<e이기 때문에 s가 가리키는 5와 e가 가리키는 1을 바꾸고 s를 1 증가시키고, e를 1 감소시킵니다.

 

 

 다음에 s<e이므로, s가 가리키는 3과, e가 가리키는 1을 바꿉니다.

 

 

 s와 e가 같으므로 끝냅니다. 따라서 5 1 5 3 2 2 1의 다음 순열은 5 2 1 1 2 3 5입니다. 정리해 봅시다. 저는 다음 순열을 먼저 판단 문제로 접근하였습니다. 그것의 복잡도가 대략 O(n^2)였습니다. 이것을 규칙을 간단히 찾기만 하면 O(nlogn)으로 줄일 수 있었습니다. 뒤에서부터 보았을 때, arr[i] < arr[i+1]인 최초의 지점만 찾으면 되기 때문입니다. 그러면 구간 [i+1, n)은 내림차순으로 정렬이 되어 있을 겁니다.

 

 이미 내림차순으로 정렬이 된 경우, 오름차로 정렬하기 위해서, O(nlogn)의 복잡도를 가지는 sort를 호출하기에는 오버헤드가 조금 있습니다. 그렇기 때문에, 적절히 swap을 해 주고, 두 개의 포인터를 추가로 주면서 바꿨던 것이고요. 그러면 O(n)으로 줄일 수 있습니다. 보통 c++에서는 뒤집을 때 reverse를 씁니다. 이 부분을 천천히 이해하신다면, c++ reference 사이트에서의 next permutation 코드도 이해하실 수 있을 겁니다.