[Leetcode] 556. Next Greater Element III

https://leetcode.com/problems/next-greater-element-iii/description/

어떤 숫자가 주어지고 각 자릿수를 적절히 재배치하여 해당 숫자보다 큰 가장 작은 수를 만들어내는 코드를 찾아야한다.
그런 숫자 찾지 못하거나 32bit 정수로 표현할 수 없으면 -1을 반환해야한다.

시도 - 1

처음에는 "가장 작은 수"라는 거를 제대로 안 보고

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        s = int(''.join(map(str,sorted(list(str(n)), reverse=True))))
        return s if s > n else -1

그냥 자릿수별로 잘라서 리스트 만든 후에 정렬시켜버렸는데 당연히 틀렸다.

시도 - 2

계속 틀려서 Submissions를 참고해서 문제를 풀었다.

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        s = list(str(n))
        
        i = len(s) - 2
        for i in range(i, -1, -1):
            if s[i] < s[i+1]:
                break
        else:
            return -1

    
        for j in range(len(s)-1, i, -1):
            if s[j] > s[i]:
                s[j], s[i] = s[i], s[j]
                break
        
        s = s[:i+1] + sorted(s[i+1:])
        answer = int(''.join(s))
        return answer if answer <= 2 ** 31 - 1 else -1

gpt의 도움을 받아서 수정을 거듭해서 겨우 통과한 코드인데 for-else 구문을 처음 알았다. for문이 정상적으로 종료되면 else에서 받아서 진행해주는 방식이다. break로 중간에 탈출하면 else는 작동하지 않는다.
여튼 숫자를 리스트로 바꾼 후 첫 for문에서 local maximum을 찾아낸다. 뒤에서부터 숫자가 증가하다가 갑자기 작아지는 부분을 찾아서 해당 부분을 저장해줬다.
이 때 아무것도 없으면 즉 끝까지 자릿수가 올라갈 수록 증가하는 패턴이라면 -1을 반환해줬다.

그러고나서 다시 뒤에서부터 탐색을 하는데 아까 찾은 작은 수보다 큰 수를 발견하면 해당 수와 자리를 바꿔주고, 그 뒷부분은 오름차순으로 정렬해줌으로써 가장 작은 수를 찾아줬다. 라고 gpt가 설명을 했는데 아직 이해가 잘 가지 않는다. 왜 굳이 sort를 해줘야하는지. 조금 더 고민해봐야겠다.