루미 알고리즘

#1264골드The Mail Carrier

PO 1999 학교 예선코딩출제 Håkan Strömberg영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

The mail carrier Harry Kuvert is careless. When he today stands at the beginning of the street along which he is to deliver the post, he has not sorted the letters.

When he reads the letter on top of the pile, he has two choices:

  • Either he puts the letter in his bag to possibly deliver it tomorrow
  • Or he finds the correct address and delivers the letter

Since Harry lives at the end of the street, he refuses to turn around and go back. The letters that end up on top of the pile and whose address he has already passed therefore go directly into the bag. Despite everything, Harry has a little mail carrier's heart that beats a little extra when he manages, using his method, to deliver as many letters as possible.

Write a program that receives a string of uppercase letters A-Z, where no letter can appear more than once. The number of letters can vary but cannot exceed 26. This string describes Harry's pile of letters, with the top letter first. Since the street is “numbered” from A to Z, the program should find the longest subsequence of the string where the letters are in ascending order. This subsequence gives the maximum possible number of delivered letters — something Harry can achieve if he always makes the right choice.

Input

The input is a string S (1 ≤ |S| ≤ 26) consisting of uppercase letters A-Z. Each letter appears at most once in the string.

Output

Output the longest string that is a subsequence of the input string such that all letters are in alphabetical order. If there are multiple equally good solutions, it suffices to output any of them.

예제

예제 1

입력
KBWZSROCFUJDEILANTMYGVXHPQ
출력
BCDEILNTVX

출처 표기

출처: Programmeringsolympiaden 1999년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.