문제 설명

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

  1. s에서 일부 문자를 선택해 새로운 문자열을 만듭니다.
  2. 단, 이때 문자의 순서는 뒤바꾸지 않습니다.

예를 들어 문자열 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입니다.

나의 풀이

첫번째 풀이

소스

def solution(s):
    stack = []

    for c in s:
        if not stack:
            stack.append(c)
            continue

        if stack[-1] < c:
            stack.pop()

        stack.append(c)

    return ''.join(stack

설명

  • Stack이용해서 마지막에 있는 문자열보다 새로들어오는 문자열이 크면 바꿔주는 방식 사용.

결과

일부분 틀림 (많이…)

리뷰

  • stack의 top에 해당하는 값이 c보다 작을 경우 계속 지워야 합니다. :) edcbakjih를 예로들면,

    1. edcba <- 여기까지 입력됩니다.
    2. edcba k <- top인 a가 k보다 작기 때문에 pop 됩니다.
    3. edcb k <- top인 b가 k보다 작기 때문에 pop 됩니다. …
    4. k <- k만 남습니다.
    5. kjih <- 그 이후로 k보다 큰 값은 안나오기 때문에 쭉 추가됩니다.

  • stack의 top에 해당하는 값이 c보다 작을 경우 계속 지워줘야 합니다. while을 이용하면 다음과 같이 코드를 작성할 수 있습니다.

    def solution(s):
  stack = []

  for c in s:
      while stack and stack[-1] < c:
          stack.pop()
      stack.append(c)

  return ''.join(stack)

두번째 풀이

소스

def solution(s):
    stack = []

    for c in s:
        while stack and stack[-1] < c:
            stack.pop()

        stack.append(c)

    return ''.join(stack)

설명

  • 리뷰 반영하여 작은것이 계속해서 있으면 계속해서 pop하는 방식으로 바꿨다.

결과

통과

스터디 리더의 풀이

def solution(s):
    stack = []

    for c in s:
        while stack and stack[-1] < c:
            stack.pop()
        stack.append(c)

    return ''.join(stack)