[리트코드][JAVA] 556. next-greater-element-iii (더 큰 요소 III)

💡 문제
next-greater-element-iii (https://leetcode.com/problems/next-greater-element-iii/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

1. 순열 (Permutation)

• 순열은 주어진 요소들을 순서를 바꾸어 나열하는 것을 의미합니다.
• 다음 순열 알고리즘: 순열을 다루는 중요한 알고리즘으로, 현재 순열의 다음으로 큰 순열을 찾는 알고리즘입니다. 주로 배열이나 리스트에서 사용됩니다.

2. 이진 검색 (Binary Search)

• 이진 검색은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘입니다.
• 이진 검색의 활용: 다음 순열을 찾는 과정에서도 이진 검색을 활용하여 다음으로 큰 순열을 찾는데 유용하게 사용될 수 있습니다.

---

🤓 문제 풀이

🔨 문제 설명

제목:556. 더 큰 요소 III

문제: 양의 정수 n이 주어졌을 때, 주어진 n과 같은 자릿수를 가지면서 n보다 큰 가장 작은 정수를 찾는 문제입니다. 만약 그런 정수가 존재하지 않는다면 -1을 반환합니다.

반환하는 정수는 32비트 정수 범위에 있어야 합니다. 만약 유효한 정수가 존재하지만 32비트 정수 범위를 넘는다면 -1을 반환합니다.

 

• 숫자를 배열로 변환:
  • "find the smallest integer which has exactly the same digits existing in the integer n"
    • 여기서 숫자 n을 문자열로 변환한 후 각 문자를 배열로 변환합니다. 이는 n의 각 자리 숫자를 개별적으로 다루기 위해 필요합니다.
• 뒤에서부터 탐색하여 교환할 숫자 찾기:
  • "find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n."
    • 뒤에서부터 탐색하면서 현재 숫자보다 큰 숫자가 나오는 첫 위치를 찾습니다. 이 과정에서 교환할 숫자가 없으면 이미 가장 큰 수이므로 -1을 반환합니다.
• 교환할 숫자와 그 다음 큰 숫자 찾기:
  • "find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n."
    • 뒤에서 다시 탐색하여 digits[i]보다 큰 숫자를 찾고 두 숫자를 교환합니다. 이 과정은 교환 후에 숫자를 오름차순으로 만들기 위한 전 단계입니다.
• 뒤쪽 부분 정렬:
  • "find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n."
    • 교환한 뒤의 숫자들을 오름차순으로 정렬하여 가장 작은 수를 만듭니다. 이는 digits[i]보다 큰 숫자를 찾고 나머지 숫자들을 정렬함으로써 가능한 가장 작은 수를 만드는 과정입니다.
• 결과 생성 및 반환:
  • "the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1."
  • 배열을 다시 숫자로 변환한 후, 결과가 32비트 정수 범위를 벗어나지 않는지 확인합니다. 결과가 범위를 벗어나면 -1을 반환합니다.

---

🔨 접근 방법

• 숫자를 배열로 변환: 주어진 숫자 n을 각 자리 숫자로 분리하여 배열로 변환합니다.
• 뒤에서부터 탐색: 뒤에서부터 탐색하면서 현재 숫자보다 큰 숫자를 찾습니다. 만약 현재 숫자보다 큰 숫자를 찾으면 두 숫자를 교환합니다.
• 교환 후 정렬: 교환 후에 뒤쪽 부분을 오름차순으로 정렬합니다.
• 결과 생성: 배열을 다시 숫자로 변환하여 결과를 반환합니다. 만약 결과가 32비트 정수 범위를 벗어나면 -1을 반환합니다.

---

🔨 문제 풀이 과정

1. 숫자를 배열로 변환:주어진 숫자를 문자열로 변환한 후, 각 문자를 문자 배열로 변환합니다. 이렇게 하면 각 자리 숫자를 개별적으로 다룰 수 있습니다. n이 1234라면, digits는 ['1', '2', '3', '4']가 됩니다.
2. 뒤에서부터 탐색하여 교환할 숫자 찾기:배열의 끝에서부터 탐색하면서 현재 숫자가 다음 숫자보다 크거나 같은 경우 인덱스를 감소시킵니다. 만약 끝까지 탐색했는데 교환할 숫자가 없다면 이미 가능한 가장 큰 수이므로 -1을 반환합니다.
   예를 들어, digits가 ['1', '2', '3', '4']일 때, i는 2가 됩니다 
3. 교환할 숫자와 그 다음 큰 숫자 찾기:뒤쪽에서 다시 탐색하여 digits[i]보다 큰 숫자를 찾고, 두 숫자를 교환합니다.
   예를 들어, digits가 ['1', '2', '3', '4']일 때, j는 3가 됩니다 (digits[3] == '4'). 교환 후 digits는 ['1', '2', '4', '3']가 됩니다.
4. 뒤쪽 부분 정렬:교환한 뒤의 숫자들을 오름차순으로 정렬하여 가장 작은 수를 만듭니다.
   여기서는 이미 오름차순이므로 변화가 없지만, 만약 배열이 ['1', '2', '4', '3', '1']였다면, 교환 후 부분 배열 ['3', '1']이 ['1', '3']으로 정렬됩니다.
5. 결과 생성 및 반환:배열을 다시 숫자로 변환한 후, 결과가 32비트 정수 범위를 벗어나지 않는지 확인합니다.
   예를 들어, digits가 ['1', '2', '4', '3']이면, 결과는 1243이 됩니다.

---

🔨 다음 순열(Next Permutation)

다음 순열 알고리즘은 주어진 숫자 배열에서 사전순으로 다음으로 큰 숫자 배열을 찾는 방법입니다. 이 알고리즘은 다음과 같은 단계로 이루어집니다:

1. 가장 긴 감소 수열을 찾기: 배열의 끝에서부터 시작하여 가장 긴 감소하는 부분 수열을 찾습니다. 이 부분 수열은 다음 순열을 찾기 위해 필요합니다. 이 부분 수열의 앞부분이 변할 숫자가 됩니다.
2. 변할 숫자 찾기: 감소하는 수열의 바로 앞에 있는 숫자를 찾습니다. 이 숫자는 i번째 인덱스의 숫자입니다.
3. 교환할 숫자 찾기: i번째 숫자보다 큰 숫자 중 가장 작은 숫자를 찾습니다. 이 숫자는 j번째 인덱스의 숫자입니다.
4. 숫자 교환: i번째 숫자와 j번째 숫자를 교환합니다.
5. 부분 수열 정렬: i번째 숫자 뒤에 있는 숫자들을 오름차순으로 정렬합니다. 이를 통해 가능한 가장 작은 다음 순열을 만듭니다.

🔨 구현코드

class Solution {
    public int nextGreaterElement(int n) {
        // 숫자를 문자열로 변환한 후, 각 문자를 문자 배열로 변환
        char[] digits = Integer.toString(n).toCharArray();
        int i = digits.length - 2;
        
        // 첫 번째로 뒷자리 숫자보다 작은 숫자를 찾는다
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }
        
        // 그런 숫자가 없으면, 이미 가장 큰 수이므로 -1 반환
        if (i < 0) {
            return -1;
        }
        
        int j = digits.length - 1;
        // digits[i]보다 큰 가장 작은 숫자를 찾는다
        while (j >= 0 && digits[j] <= digits[i]) {
            j--;
        }
        
        // 찾은 숫자들을 교환
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
        
        // i번째 이후의 숫자들을 오름차순으로 정렬
        Arrays.sort(digits, i + 1, digits.length);
        
        // 문자 배열을 다시 숫자로 변환
        long result = Long.parseLong(new String(digits));
        
        // 결과가 32비트 정수 최대값을 초과하면 -1 반환
        if (result > Integer.MAX_VALUE) {
            return -1;
        }
        
        // 결과 반환
        return (int) result;
    }
}

---

📚 풀이 보완

코드 설명

1. 숫자를 문자열로 변환:
   • 주어진 숫자 n을 문자열로 변환한 후, 각 문자를 문자 배열로 변환합니다. 예를 들어, n = 1234이면 digits는 ['1', '2', '3', '4']가 됩니다.
2. 뒤에서부터 탐색하여 피벗 찾기:
   • 배열의 끝에서부터 탐색하여 현재 숫자가 다음 숫자보다 작은 첫 번째 위치를 찾습니다. 여기서 i는 탐색을 시작하는 인덱스입니다.
   • 예를 들어, digits = ['5', '3', '4', '2', '1']인 경우, 탐색 결과 i는 1이 됩니다 (digits[1] = '3').
3. 피벗이 없는 경우:
   • 만약 i가 음수라면, 이는 이미 가장 큰 순열이라는 뜻이므로 -1을 반환합니다.
4. 피벗보다 큰 숫자 찾기:
   • 다시 뒤에서부터 탐색하여 digits[i]보다 큰 숫자를 찾습니다. 여기서 j는 탐색을 시작하는 인덱스입니다.
   • 예를 들어, digits = ['5', '3', '4', '2', '1']이고 i = 1인 경우, 탐색 결과 j는 2가 됩니다 (digits[2] = '4').
5. 숫자 교환:
   • 찾은 두 숫자를 교환합니다.
   • 예를 들어, 교환 후 digits = ['5', '4', '3', '2', '1']가 됩니다.
6. 뒤쪽 부분 정렬:
   • i 이후의 숫자들을 오름차순으로 정렬하여 가장 작은 수를 만듭니다.
   • 예를 들어, digits = ['5', '4', '1', '2', '3']가 됩니다
7. 결과 생성 및 반환:
   • 정렬된 문자 배열을 다시 숫자로 변환합니다. 결과가 32비트 정수 범위를 넘으면 -1을 반환하고, 그렇지 않으면 결과를 반환합니다.
   • 예를 들어, digits = ['5', '4', '1', '2', '3']이면, 결과는 54123이 됩니다.

---

📍 Plus+

시간 복잡도

• 배열을 뒤에서부터 탐색하는 두 번의 반복문은 O(n)입니다.
• 마지막에 부분 배열을 정렬하는 데 드는 시간은 최악의 경우 O(n log n)입니다.
• 전체 시간 복잡도는 O(n) + O(n) + O(n log n) = O(n log n)입니다.
• 따라서 최종적인 시간 복잡도는 O(n log n)입니다.

공간 복잡도

• 여기서 n은 숫자의 자릿수입니다.
• 숫자를 문자 배열로 변환하여 저장하고, 추가적으로 배열을 정렬하기 위해 임시 공간을 사용합니다. 따라서 문자 배열과 정렬에 필요한 공간을 고려하여 공간 복잡도는 O(n)입니다.

요약

• 시간복잡도: O(n log n)
• 공간복잡도: O(n)

 

---

풀이 참고 로직