문제 설명

Next Permutation - LeetCode

주어진 숫자 배열 nums에 대해 사전순(lexicographically)으로 다음 순열을 찾는 문제입니다.

  • 현재 순열보다 크면서 가장 작은 값이 되는 순열을 찾기
  • 제자리(in-place)에서 변경해야 하며, 추가 배열을 사용하지 않아야 함
  • 가장 큰 순열이면 가장 작은 순열로 변경 (예: [3, 2, 1] → [1, 2, 3])

✅ 제약 조건:

  • 1 ≤ nums.length ≤ 100
  • 0 ≤ nums[i] ≤ 100

해설

1️⃣ 브루트포스 (O(N!)) → 비효율적

  • 모든 순열을 생성한 후, 현재 순열 다음 값을 찾음
  • 매우 비효율적 → 사용하지 않음

2️⃣ 최적화된 O(N) 풀이 (그리디 + 정렬) [추천]

✔ 순열의 다음 값은 다음과 같은 과정으로 구할 수 있음

  1. 뒤에서부터 (오른쪽에서) 내림차순이 아닌 지점(i)을 찾기
    • nums[i] < nums[i+1]인 가장 큰 i를 찾음
    • 이 값은 더 큰 숫자로 교체될 값
  2. i보다 오른쪽에서 nums[i]보다 큰 숫자(j)를 찾기
    • nums[j] > nums[i]인 가장 큰 j 찾기
  3. nums[i]와 nums[j]를 swap
    • 즉, 더 큰 숫자로 변경
  4. i+1부터 끝까지 오름차순 정렬
    • 가장 작은 다음 순열을 만들기 위해 정렬 (사실상 뒤집기)

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def nextPermutation(nums):
    n = len(nums)
    
    # Step 1: 뒤에서부터 내림차순이 아닌 첫 번째 위치 찾기
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    
    if i >= 0:  # 내림차순이 아닌 위치가 있으면
        # Step 2: nums[i]보다 큰 숫자를 뒤에서부터 찾기
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # Step 3: Swap
        nums[i], nums[j] = nums[j], nums[i]

    # Step 4: i+1부터 끝까지 오름차순 정렬 (뒤집기)
    nums[i + 1:] = reversed(nums[i + 1:])

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

var nextPermutation = function(nums) {
    let i = nums.length - 2;
    
    // Step 1: 뒤에서부터 내림차순이 아닌 첫 번째 위치 찾기
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) { // 내림차순이 아닌 위치가 있으면
        let j = nums.length - 1;
        // Step 2: nums[i]보다 큰 숫자를 뒤에서부터 찾기
        while (nums[j] <= nums[i]) {
            j--;
        }
        // Step 3: Swap
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }

    // Step 4: i+1부터 끝까지 오름차순 정렬 (뒤집기)
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform