문제
문자열 s로 만들 수 있는 부분 문자열 중 사전 순 가장 뒤에 나오는 문자열 찾기
s의 순서는 바꾸지 않음
문자열 s의 길이 : 1이상 1,000,000 이하
문자열은 모두 소문자로 이루어짐
입출력 예시
| s | return |
|---|---|
| “xyb” | “yb” |
접근
이전 문자열보다 큰 문자가 나오면 이전 문자열 중 현재 문자보다 작은 문자를 모두 지워주는 식으로 구현한다.
원래 while이 아닌 if로 구현했는데 이 경우 이전 문자 한개만을 비교하기 때문에 정답을 못찾을 수 있다.
예를 들어, aabb의 경우 b에서 a하나만 검사하고 넘어가기 때문에 a 두개를 지우지 못한다.
따라서 while문을 이용하여 현재 문자보다 큰 문자를 만나기전까지 이전 문자들을 모두 검사해주어야 한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
def solution(s):
lst = []
for i in s:
while len(lst) > 0 and lst[-1] < i:
lst.pop()
lst.append(i)
answer = ''.join(lst)
return answer