[BOJ] 백준 16719 ZOAC (Swift)

문제

https://www.acmicpc.net/problem/16719

16719번: ZOAC

풀이

사전 순으로 가장 앞에 오도록 하는 문자를 선택 해야 하는데, 그렇다면 선택되지 않은 문자중 가장 빠른 문자를 선택해야 할 것
그 이후에는 선택된 문자로부터 오른쪽에 있는 문자를 선택해야 사전 순으로 더 앞설 것임

BAB라는 문자열이 입력으로 주어졌을 때를 예로 들어보자.

밑에 적은 숫자는 index 숫자에요.

맨 처음에는 당연히 A가 선택되겠죠?

왼쪽에 있는 B를 선택했을 때는 BA,
오른쪽에 있는 B를 선택했을 때는 AB
로 AB가 사전순으로 가장 앞서는 문자열이 됩니다.

따라서 선택된 문자로부터 오른쪽에 있는 문자를 선택해야겠네요!

그러면 사전순으로 같은 문자가 있을 때는 왼쪽을 먼저 선택해야 할까요? 오른쪽을 먼저 선택해야할까요?

DABDAC

두번째 선택까지 했다면 AA 가 사전순으로 가장 앞서는 문자열이 될 것이에요.
저희는 선택된 문자로부터 오른쪽에 있는 문자를 선택하기로 했었죠?
그러면 당연히 사전순으로 같은 문자가 있을 때, 왼쪽의 문자를 먼저 선택해야 할 것이에요.
그래야 자연스럽게 선택된 문자의 오른쪽 문자들을 탐색하게 될 것 입니다.

이제 문제 예제입력3을 예시로 들어서 풀이해보겠습니다.

가장 먼저 A가 선택되고 A를 출력할 것입니다.
Step1: A

그 이후에는 A로 부터 오른쪽과 왼쪽으로 나누어서 탐색할거에요.

A의 오른쪽 인덱스부터 마지막까지 살펴보면 I가 가장 사전순으로 앞서는 문자열이에요.
Step2: AI

이제 I의 오른쪽 인덱스부터 탐색하겠습니다.

K가 사전순으로 가장 앞서기 때문에 K를 선택합니다.
Step3: AIK

이제 K를 기준으로 오른쪽을 살펴보려고 하는데, 배열이 끝이 났습니다.
이제 K를 기준으로 왼쪽을 살펴보면 되겠죠?

Step4: AINK

이제 I를 기준으로 오른쪽 인덱스는 모두 탐색이 끝났습니다.
I를 기준으로 하는 왼쪽 인덱스를 탐색해주면 되겠죠? (3...5)

Step5: ALINK

L을 기준으로 하는 오른쪽 인덱스는 없네요.
L의 왼쪽을 탐색해주겠습니다. (3..4)

Step6: ARLINK

다음은 R을 기준으로 하는 오른쪽 인덱스에 1개의 문자가 남아있네요!

Step7: ARTLINK

이제 A를 기준으로 왼쪽 인덱스에 대해서 탐색해주겠습니다. (0...1)

Step8: SARTLINK

자 이제 마지막입니다.
S를 기준으로 오른쪽 인덱스를 탐색해줍니다.
단 하나 남았네요.

Step9: STARTLINK

이제 모든 문자를 탐색했어요!

이 순서대로 출력해주면 되겠죠?

저는 확인을 했는지 안했는지 [Bool] 자료형으로 체크를 해주고, 탐색을 한 번 할때마다, 인덱스를 돌면서 체크가 되어있다면 출력해주도록 코드를 짰습니다.

또한 재귀로 탐색할 range를 정해서 탐색을 계속해서 이어나갔어요.
재귀를 탈출할 조건은 더이상 탐색할 부분이 없어야 탈출이 되겠죠?
left와 right 변수를 두고, left가 right값과 같거나 크다면 탐색할 부분이 없다고 판단했습니다.

소스코드로 확인해보시죠!

소스코드

후기

• 생각보다 어려웠다..🤣
• 무조건 선택된 문자보다 오른쪽을 기준으로 탐색한다는 것이 약간 그리디적인 관점이 있는 것 같다..