E

문제 설명:

주어진 문자열에 포함된 문자들을 적절히 배열하여 Max(1~i번째 문자까지의 suffix와 prefix가 같은 길이)가 최소가 되게 하고, 그러한 문자열이 여러개 있으면 사전순으로 가장 앞에 오는 것을 출력하라.

문제 해설:

이 문제는 별다른 관찰이 필요 없이 경우들을 나누어서 풀면 된다.

하나만 등장하는 문자가 존재하는 경우:

알파벳 순으로 가장 빠른 그러한 수를 맨 처음에 넣고 나머지는 정렬해서 출력

이유: 무조건 f(s)=0이기 때문.

a-2<=n-a 인 경우 (a=처음 등장하는 문자 개수):

처음 a 2개 출력 후, 다른 수 1개, a 1개 순으로 출력 (ex: aabacaca… )(a=처음 등장하는 문자)

이유: 어차피 f(s)=1이 되어야 하고, a를 2개 배치한다면 사전순으로 최소. 그러나 앞의 조건에 맞아야 a를 두개 배치할 수 있음.

문자 종류가 3개 이상인 경우:

ab출력 후 a전부 , c, b전부, 나머지 정렬해서 출력(ex: aba…cb…c…)

이유: 위와 같이 어차피 f(s)=1이 되어야 하고, a를 2개 배치할 수 없다면 b를 배치해야 하는데, a와 b외의 문자가 존재한다면 ab다음에 a가 와도 a…와 b…를 연결하는 부분에 끼워넣어 ab가 등장하는 것을 막을 수 있음.

그 외:

a 하나 출력 후 b전부, a전부(ex: ab…a…)

이유: 문자가 두 종류밖에 없으므로 이것이 최소이다. a가 b앞에 2개 이상 존재한다면 f(s)>1이 되기 때문에 앞에 a는 하나밖에 올 수 없다.