[백준 13417] 카드 문자열

Greedy Algorithm과 ord() 함수를 사용하면 해결되는 문제입니다.

문제의 조건들을 차례대로 살펴봅시다.

N개의 카드가 일렬로 놓여있는데 왼쪽부터 차례대로 한 장씩 가져옵니다.

여기서 다양한 자료구조를 생각할 수 있는데
우리는 이 글자들을 하나의 list에 담아놓은 다음 for문을 통해 하나씩 꺼내오기로 합시다.

그 다음부터는 가져온 카드를 기존에 놓인 카드들의 ‘가장 왼쪽’ 또는 ‘가장 오른쪽’에 놓습니다.

사전순으로 가장 빠른 문자열을 구합니다.

위의 조건들을 종합하여 살펴보면
입력되는 문자들을 cards라는 하나의 list에 담아놓고
답으로 출력할 ans라는 문자열을 미리 cards[0]으로 초기화합니다. (맨 앞 글자는 어차피 무조건 추가될 것이므로)
그 후, for문을 통해 문자들을 차례대로 하나씩 꺼내오면서
문자의 ASCII code를 반환하는 ord() 함수로 기존에 놓여있던 카드들인 ans의 첫 글자와 ASCII code를 비교합니다.
이때, 꺼내온 글자의 ASCII code가 더 작다면 사전순으로 더 앞선다는 것을 의미하므로
ans의 가장 왼쪽에 더해주면 되며,
ans의 첫 글자의 ASCII code가 더 작다면 사전순으로 뒤라는 것을 의미하므로
ans의 가장 오른쪽에 더해주면 됩니다.

for문이 종료되면, 최종적인 답 ans를 출력하면 됩니다.
글자들을 하나씩 꺼내서 ans에 추가하는 과정에서 ASCII code를 비교하는 것이
그 당시에 가장 최선인 선택을 해나가는 알고리즘, 즉 Greedy Algorithm을 사용한 것입니다.

문제 : 백준 13417 - 카드 문자열