문제 설명 📑

어떤 문자열 s가 주어졌을 때, s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 찾으려 합니다. 부분 문자열을 만드는 방법은 다음과 같습니다. s에서 일부 문자를 선택해 새로운 문자열을 만듭니다. 단, 이때 문자의 순서는 뒤바꾸지 않습니다. 예를 들어 문자열 “xyb”로 만들 수 있는 부분 문자열은 다음과 같습니다. x y b xy xb yb xyb 이 중 사전 순으로 가장 뒤에 있는 문자열은 “yb”입니다. 문자열 s가 주어졌을 때 s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 리턴하는 solution 함수를 완성해주세요.

제한사항 🚫

s는 길이가 1 이상 1,000,000 이하인 문자열입니다. s는 알파벳 소문자로만 이루어져 있습니다.

문제 풀이 👩🏻‍💻

리뷰 반영 전

리뷰 반영 후

• 알파벳 : index를 키와 value 쌍으로 dictionary를 만들어주지 않아도 알파벳 자체를 비교할 수 있으므로(아스키코드 확인하면 a는 97, z는 122이므로 비교 가능) 바로 알파벳끼리 비교해가며 stack에 추가하거나 pop

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 사전순 부분문자열
def solution(s):
    string_stack = []

    for i in s:
        # string_stack이 비어있지 않으며, stack의 최상단 요소가 i보다 작으면
        # 최상단 요소를 pop
        # (알파벳끼리 비교했을 때 더 작은 쪽이 사전 순으로 우선)
        while string_stack and string_stack[-1] < i:
            string_stack.pop()
        # 최상단 요소가 i보다 크면 i보다 사전 순으로 더 뒤에 나오므로
        # i를 stack에 추가
        string_stack.append(i)

    return ''.join(string_stack)

문제 출처