(프로그래머스) 사전 부분문자열

문제 설명

어떤 문자열 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):
    answer = ''
    checks = list(s)
    max_idx = -1
    
    while True:
        try:
            checks = checks[max_idx + 1:]
            max_chr = max(checks) # 가장 큰 문자열
            max_idx = checks.index(max_chr) # 가장 큰 문자열의 인덱스
            answer += max_chr
        except ValueError:
            break
    
    return answer

 

처음 생각대로 구현한 방식은 위와 같다. 

가장 큰 문자열의 index를 구하여 리스트를 슬라이싱 하는 방법을 사용하였는데 

아마 max_chr와, max_idx를 구하는 부분에서 시간초과가 발생하는 것 같다.

 

 

통과한 소스

def solution(s):
    result = []
    for chr in s:
        while result and result[-1] < chr:
            result.pop()
        result.append(chr)
    return ''.join(result)

 

원리는 간단하다.

1. 주어진 문자열을 하나씩 루프돌며 result 스택에 넣는다.
2. result 스택이 비어있지 않고, 현재 확인하고 있는 문자가 스택의 가장 마지막 요소보다 클 경우 pop 하고 현재 문자를 result 스택에 넣는다.
3. 맨 처음에는 for문안에서 if len(result) > 0 and result[-1] < chr 로 비교하였는데, 이렇게 할 경우 스택의 가장 마지막 요소만 비교하고 넘어가게 된다. 하지만 스택안에 현재 확인하고 있는 문자보다 작은 문자가 있을수 있기 때문에 while 문으로 확인해야 한다.