카카오_해커랭크_medium 35p_Bigger is Greater_next_purmutations()

next_permutations()는 C++에만 있음

• 그래서 python은 구현을 따로 해야함 (아래 솔루션 코드 있음)

• 링크 : https://www.hackerrank.com/challenges/bigger-is-greater/problem?isFullScreen=true

---

메모한 것

간단한 문자열 비교 문제임(=숫자처럼 비교됨)

분명 쉬운문제인데 왜 틀린가 했더니

• 주어진 문자열보다 큰 것 중에서 제일 작은것 이었음...
  • 큰것만 리스트에 넣어주고
  • 그중에서 min값을 출력
• 풀었는데 시간초과뜸...
  • C++에 있는 next_permutations()함수를 사용하면 바로 풀리는 문제였음

---

솔루션 코드1 - 그냥 permutations()쓴 버전

• 3개 히든케이스 시간초과

from itertools import permutations

def biggerIsGreater(w):
    leng = len(w)
    flag = False
    ans = []
    for i in permutations(w, leng):
        tmp = "".join(map(str,i))
        if w < tmp:
            ans.append(tmp)
            
    if not ans:
        return "no answer"
    else:
        return min(ans)
        
print(biggerIsGreater('dkhc'))

---

솔루션 코드2 - next_permutations()쓴 버전

• 원래 통과여야 하는데 실행 안해봄
  • next_permutations() 함수 그대로 사용하면 된다
• 링크1 : https://pololove.tistory.com/m/87
• 링크2 : https://copy-driven-dev.tistory.com/entry/nextpermutation-Python-%EA%B5%AC%ED%98%84

s = list(input())

def biggerIsGreater(arr):
    i,j = len(arr)-1, len(arr)-1
    
    #증가하는 형태를 찾을때까지
    while i > 0 and arr[i-1] >= arr[i]:
        i -= 1
        
    if i == 0:
        return False
    
    while arr[i-1] >= arr[j]:
            j -= 1
            
    arr[i-1], arr[j] = arr[j], arr[i-1]
    
    k = len(arr)-1
    
    #엇갈릴 때까지
    while i < k:
        arr[i],arr[k] = arr[k],arr[i]
        i += 1
        k -= 1
    answer = "".join(map(str,arr))
    return answer

print(biggerIsGreater(s))