Golang: next permutation을 구현해보자

Photo by Jean-Louis Paulin on Unsplash

 

 

LeetCode 문제를 푸는데 풀기가 쉽지 않았다. discuss를 보니 next permutation을 계산하는 것 자체는 기본으로 알고 있는 것으로 하고 넘어가고 있었고, 어떤 언어는 기본으로 제공하는 함수였다. 그럼에도 자괴감을 힘겹게 극복하고 next permutation을 이해해보고 Go로 구현해보았다.

개념 이해

개념 이해 링크: https://bit.ly/3bvWZmu

 

우리가 구현하려는 것은 다음과 같다. 정수 슬라이스가 있다고 할때에 그 슬라이스 순서대로 하나의 수라고 생각해보자. 그러면 이 수의 각각의 자릿수의 순서만을 바꿔서 그 다음 큰 수를 찾는 것이다. 예를 들어 12345 라는 숫자가 있다면, 1, 2, 3, 4, 5를 이용해서 이보다 큰 숫자중 가장 작은 숫자를 만든다면 12354가 될 것이다.

말로 풀어내려니 복잡한데 위 링크를 따라 이해하는 것이 한결 쉬울 것이다.

구현의 단계

1. 우선은 높은 자리의 숫자(슬라이스의 왼쪽)가 낮은 자리의 숫자(슬라이스의 오른쪽)보다 작은 경우를 찾아야 한다.

 

1. 낮은 자리, 즉 슬라이스의 맨 뒤쪽부터 찾아 올라간다.

이렇게 i번째 index를 찾았다면 i+1번째부터 끝까지의 숫자는 내림차순(descending) 정렬이 되어있다.

 

예를 들어 398765432 라는 숫자라면, 뒤쪽부터 찾아 올라갈때에 계속 앞자리가 더 큰 숫자이다가 3을 만나고서야 멈춘다. 그러면 3 뒤쪽의 98765432 는 내림차순 정렬이다.

 

2. 그러고 나면 이제부터는 i+1부터 끝까지의 숫자들 중에서 i 인덱스의 값보다는 큰데 가장 작은 값을 찾아야 한다.

1) i+1 인덱스 이후는 내림차순 정렬이 되어있으니, 맨 뒤부터 i 인덱스값보다 큰걸 찾으면 된다.

2) 그렇게 찾은 j 인덱스로 i, j 인덱스의 값을 바꿔준다.

 

위의 예시라면 3과 4를 바꿔준다 그러면 498765332가 된다. 중요한건 98765332 역시 내림차순 정렬이 되어 있다는 것.

 

3. 이제 마지막 작업이다. 위에 언급한대로 i+1부터 끝까지의 슬라이스는 내림차순 정렬이 되어있다.

1) 그러니 이것을 오름차순으로 뒤집어서 정렬해주면

2) i 인덱스의 값으로 시작하는 다음 순열의 값은 가능한 가장 작은 숫자가 되는 것이다.

실제 구현

Go PlayGround: https://play.golang.org/p/vUirkptzyIE

 

핵심 부분만 보자

1. 들어온 inputnums 슬라이스를 바로 copy 했다. 들어온 슬라이스를 immutable하게 유지해주고 싶어서 이렇게 구현했다

2. 먼저 찾아야 하는 것은 뒤에서부터 처음으로 다음 값보다 작아지는 인덱스 i와, 그렇게 찾은 인덱스 i + 1 부터 끝까지의 값중에서 i 인덱스의 값보다는 크지만 가장 작은 값이 있는 위치인 j이다.

3. 그렇게 찾고나면, i, j 위치의 값을 바꾼다

4. 마지막으로 i+1 인덱스 위치부터 끝까지의 값을 뒤집어준다.

 

// let's not modify the input
func nextPermutation(inputnums []int) []int {

	nums := make([]int, len(inputnums))
	copy(nums, inputnums)
	var i, j int

	// find the latest index i
	// which value is larger then the value of i+1
	for i = len(nums) - 2; nums[i] > nums[i+1] && i > 0; i-- {
	}

	// it is already the largest number. no next permutation.
	// so go back to the smallest number
	if i == 0 {
		reverse(nums)
		return nums
	}

	// find the latest index j (range: i < j < len(nums)-1)
	// which value is larger then the value of i
	for j = len(nums) - 1; j > i && nums[i] > nums[j]; j-- {
	}

	// swap the value of the index i and j
	// the value of the index j is the smallest value
	// but larger then the value of the i
	nums[i], nums[j] = nums[j], nums[i]

	// then reverse the rest of the slice
	reverse(nums[i+1:])
	return nums
}

끝