[Medium] 556. Next Greater Element III

문제

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

Next Greater Element III - LeetCode

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note that 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.

 

양의 정수 n이 주어지면, 정수 n에 존재하는 숫자와 정확히 같은 숫자와 n보다 큰 가장 작은 정수를 구하라. 이러한 양의 정수가 없으면 -1을 반환합니다.
반환된 정수는 32비트 정수에 맞아야 합니다. 유효한 답이 있지만 32비트 정수에 맞지 않으면 -1을 반환합니다.

 

예시

Example 1:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

 

제약 조건

Constraints:

• 1 <= n <= 231 - 1

 

해결 과정

n 숫자를 nums 배열로 변환한다.

max, idx 값을 -1로 초기화한다.

 

for문을 돌며 max의 idx를 저장한다.

max 값이 없다면 return -1를 한다.

 

secondHalf 변수에 idx를 기준으로 배열로 자르고 내림차순 정렬한다.

예를 들어 12의 값을 splice 했다면 secondHalf에는 2가, nums에는 1이 남게 된다.

 

가장 큰 숫자를 그 아래 자리 수에 배치해야 하기 때문에 nums에 남아있는 숫자들을 순회하면 자리를 바꾼다.

nums와 secondHalf를 합하여 result 변수에 할당한다.

이때 result 값이 bigint가 되면 -1을, 아니면 result의 값을 반환한다.

 

해결 코드

/**
 * @param {number} n
 * @return {number}
 */
var nextGreaterElement = function(n) {    
    let nums = n.toString(10).split("").map(el => Number(el))    
    let max = -1, idx = -1
    
    for(let i = nums.length - 1; i >= 0; i--){
        if(nums[i] < max){
            idx = i;
            break;
        }
        max = Math.max(max, nums[i]);
    }
    
    if(idx === -1)return -1
    
    let secondHalf = nums.splice(idx + 1).sort((a,b) => a - b)
    
    for(let i = 0; i < secondHalf.length; i++){
        if(secondHalf[i] > nums[idx]){
            [nums[idx], secondHalf[i]] = [secondHalf[i], nums[idx]]
            break;
        }
    }        
    
    let result = +nums.concat(secondHalf).join("");
    let max32BitInt = 2147483647;
    return result > max32BitInt ? -1 : result
};