[자료구조] 사전순 부분문자열 파이썬

from itertools import combinations
def solution(s):
    s = list(s)
    big = max(s)
    # print(big)
    for i in range(1, len(s)+1):
        C = combinations(list(s),i)
        C = ["".join(x) for x in list(C)]
        
        big = max(C+ [big])
        
    return big

max는 iterable로 받기 때문에 C와 big을 리스트로 변환한것을 하나의 list로 해서 넘겨줘서 해결이 되었는데

 

시간 초과가 발생함

 

combination이랑 max쪽에서 발생한거 같은데

 

앞선 문제처럼 heap으로 풀어야 하나.

---

이것도 stack 이용하면 풀린다...

 

순서를 요구한다면 for문을 사용한 stack을 생각해야 한다는 것을 명심하자

def solution(s):
    stack = []
    for elem in s:
        while len(stack) > 0 and stack[-1] < elem:
            stack.pop()
        stack.append(elem)
    return "".join(stack)

출처: lar542.github.io/Practice/2019-07-02-practice2/