99클럽 코테 스터디 20일차 TIL Leetcode Next Greater Element III

Leetcode Next Greater Element III

같은 숫자 조합으로 자신보다 큰 수가 있는지 확인하는 문제.

수학적?으로 생각해 볼때, 가장 큰 수는 내림차순으로 정렬된다.

그런 원리를 이용해서 뒤에서 부터 오름차순이 끊기는 부분까지 구한 뒤에, 해당 부분에서 다음 큰수를 구하면 된다.

끊기는 부분이랑 자신보다 큰 숫자 위치를 바꿔주고 나머지 부분을 정렬해서 가장 작은 숫자로 만들면 정답이 완성되는데, 

깔끔하게 짜는 것이 생각이 나지않아 좀 지저분하게 풀었다.

코테 감이 떨어지는 것 같기도하고.. 일단은 다른게 더 중요해서 시간안에 잘 풀었다는 것에 만족하고 추후에 다시 또 풀어봐야겠다.

나의 코드

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        N=str(n)
        k=-1
        dic={}
        for i in range(len(N)-1,0,-1):
            l=int(N[i])
            if dic.get(l):
                dic[l]+=1
            else:
                dic[l]=1
            if N[i]>N[i-1]:
                k=i-1
                break
        if dic.get(int(N[k])):
            dic[int(N[k])]+=1
        else:
            dic[int(N[k])]=1
        if k==-1:
            return -1
        start=int(N[k])
        first=0
        for j in sorted(set(dic.keys())):
            if start<j:
                first=j
                break
        dic[first]-=1
        arr=[]
        for key,val in dic.items():
            arr.extend([key]*val)
 
        x= int(N[:k]+str(first)+"".join(map(str,sorted(arr))))
        if x>2**31-1:
            return -1
        else:
            return x