[코딩테스트 예제] 사전순 부분문자열

문제 설명
어떤 문자열 s가 주어졌을 때, s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 찾으려 합니다. 부분 문자열을 만드는 방법은 다음과 같습니다.

s에서 일부 문자를 선택해 새로운 문자열을 만듭니다.
단, 이때 문자의 순서는 뒤바꾸지 않습니다.
예를 들어 문자열 xyb로 만들 수 있는 부분 문자열은 다음과 같습니다.

x
y
b
xy
xb
yb
xyb

이 중 사전 순으로 가장 뒤에 있는 문자열은 yb입니다.

문자열 s가 주어졌을 때 s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 리턴하는 solution 함수를 완성해주세요.

제한 사항
s는 길이가 1 이상 1,000,000 이하인 문자열입니다.
s는 알파벳 소문자로만 이루어져 있습니다.
입출력 예
s result
xyb yb
yxyc yyc
입출력 예 설명
입출력 예 #1

앞서 설명한 예와 같습니다.

입출력 예 #2

yxyc로 만들 수 있는 부분 문자열은 다음과 같습니다.

y
x
c
yx
yy
yc
xy
xc
yxy
yxc
yyc
xyc
yxyc

이 중 사전 순으로 가장 뒤에 나오는 문자열은 yyc입니다.

---

처음에는 문제를 조합(combination) 모듈을 이용해 접근했는데 효율성 측면에서 매우 성능이 좋지 못했다. 그래서 고민하다가 스택을 이용하면 쉽게 해결될 듯하여 적용했다.

내가 작성한 코드

def solution(s):
    answer = ''
    
    stack =[]
    
    for i in range(len(s)):
        if len(stack) == 0:
            stack.append(s[i])
        elif stack[-1] < s[i]:
            while len(stack) > 0 and stack[-1] < s[i]:
                stack.pop()
            stack.append(s[i])
        
        elif stack[-1] >= s[i]:
            stack.append(s[i])
    
    # answer = ''.join(stack)
    return ''.join(stack)