[leetcode][31] Next Permutation 문제풀기!

---

• 문제풀러가기✈

---

👓 문제 요약

다음 순열 구해라.

자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

솔직히 말해서 다음 순열이 뭔데? 뭔데? 하면서 한 5분은 찾아봤다.

다음 순열은 예를 들면 다음과 같다.
숫자 1,2,3,4 각각 하나씩 있다. 이를 통해 순열을 만들어보면

• 1,2,3,4
• 4,3,2,1
• 2,3,1,4

등 이 가능하다.

하지만 문제에서는 lexicographically 즉 사전순서대로 순열을 만들었을 때,
해당 순열 다음으로 오는 순열이 무엇이냐?? 를 물어본 것이다.

예를 들면
1,2,3,4 의 순열들은

-   1,2,3,4
-   1,2,4,3
-   1,3,2,4
-   1,3,4,2 ....

순서로 이어진다.

단순히 모든 경우의 수를 알아보는 방법도 있겠지만... 우리는 효율적인 코딩을 목표로 하기 때문에 다른 방법을 생각해보자.

그래서 제가 어떻게 풀었냐면 !!

!!!! 탐욕기법을 사용 한다면 가능하다!

이전 순열은 무조건 이번 순열보다 작기 때문에 규칙을 적용하면 될 것 같다 뜨악!! 갑자기 고기먹고싶다.

아니 문제로 돌아와서.

1,2,3,4,5 를 예로 들어보자.

1,4,3,2,5 라는 순열이 주어졌다. 이 순열의 다음 순열은 무엇일까?

• 1, 5 로 시작할 수도 있다. 이 경우에는 1, 4 이후에 나오는 숫자들은 서로를 조합해서 만들 수 있는 순열중 가장 커야한다.
• 3, 2, 5 로 만들 수 있는 가장 큰 순열은 무엇일까? 일단 5로 시작 해야하기 때문에 조건에 만족하지 않는다.
• 1, 4 로 시작해야 한다는 말이다.

여기서 규칙을 찾을 수 있다.

• 다음 순열에서 더 큰 값을 만들기 위해서는 앞 위치에 나오는 숫자는 뒤의 숫자보다 커져야한다.

3, 2, 5 의 경우 2 가 5보다 작기 때문에 서로의 위치를 바꾸게 되면

3, 5, 2 로서 3, 2, 5 순열보다 큰 값이라는 것을 보장한다.

하지만 바로 다음 순열이라는 것은 보장하지 않는다.

예를 들어

1,2,5,4,3 가 있다고 생각하자.

2 보다 큰 숫자중 5와 바꾸어주면

1,5,2,4,3 이 된다 하지만 정답은
1,3,2,4,5 이다.

즉 단순히 큰 값이 아닌, 큰 값중 가장 작은 값을 찾아 바꿔야 한다는 것이다.

또 조건이 있다. 2 와 5 처럼 증가하는 모양을 보이는 가장 마지막 놈끼리 바꿔야 한다는 것이다.

또오오오 조건이 있다. 바꾼 후에 오른쪽에 있는 놈들은 해당 수열로 만들 수 있는 가장 큰 값이다.
가장 작은 값으로 형태를 바꾸어 주어야한다.

이건 단순히 바꾼놈 기준 오른쪽에 있는 놈들을 바깥에서 안쪽으로 전부 위치를 교환해주면 된다.

자자자 정리하자면

• 우리가 바꿀 기준인덱스는 증가하는 모양중 가장 마지막 놈의 작은 녀석이다
• 기준인덱스와 바꿀 녀석은 기준인덱스 오른쪽에 있는 놈 중 기준인덱스의 위치에 있는 놈 보다 크지만 가장 작은 값이다.
• 바꾸고 나면 기준인덱스 + 1 위치부터 바깥에서 안쪽으로 전부 위치를 바꿔 주어야한다.
• 보충 설명하면 기준인덱스 + 1 과 가장 오른쪽 놈을 교환, 기준인덱스 + 2 와 가장 오른쪽에서 - 1 놈과 교환 하라는 말이다.

🥽 소스코드 및 소스해석

var nextPermutation = function (nums) {
  let standIndex = -1;
  let changeIndex = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] < nums[i + 1]) {
      standIndex = i;
      changeIndex = i + 1;
    }
    if (nums[changeIndex] >= nums[i + 1] && nums[standIndex] < nums[i + 1]) {
      changeIndex = i + 1;
    }
  }

  if (standIndex !== -1) {
    swap(nums, standIndex, changeIndex);
  }

  let i = standIndex + 1;
  let j = nums.length - 1;
  while (i < j) {
    swap(nums, i, j);
    i++;
    j--;
  }
};

const swap = (nums, a, b) => {
  let temp = nums[a];
  nums[a] = nums[b];
  nums[b] = temp;
};

🔨 문제 후기

문제 이해하기가 어려웠다.

내 영어 능력을 의심했다.

나랑 비슷한 사람이 많을까?