문제1803--단어게임

1803: 단어게임

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 121  통과: 22
[제출] [채점기록] [묻고답하기]

문제 설명

승규와 승주가 영어 단어를 가지고 게임을 하고자 한다.
게임의 규칙은 다음과 같다.

  • 서로 턴을 번갈아가면서 진행하며, 승규 먼저 시작한다.
  • 매 턴마다 단어에 존재하는 문자를 선택하고, 이를 제거한다.  만약 'abcd'라는 단어가 있고 여기서 c를 선택할 경우 'abd'라는 단어로 바뀌게 된다.
  • 지운 문자를 현재 자신이 만들고 있는 단어의 맨 뒤에 붙인다.
  • 만약 현재까지 만든 단어가 'acm'이라고 할 때 지운 문자가 'c'이므로 'acmc'라는 단어가 만들어지게 된다. 
  • 남은 문자가 더 이상 없을 경우 게임이 끝나며, 사전 순으로 먼저 나오는 단어를 만드는 사람이 승리하게 된다.

게임을 하다 보니 승규가 매번 이기게 되어서 시시해진 나머지 승규는 선택하는 문자를 맨 오른쪽에 위치한 문자를 선택한다고 하자. 그럴 때 매번 지던 승주가 이길 수 있는 방법은 존재하는지 찾아내는 프로그램을 작성하라.

입력 설명

입력의 첫 줄에는 단어의 길이 N ( 2≤N≤100,000 )이 입력된다. N은 짝수다.

그 다음 줄에는 N개의 영문 소문자로 이뤄진 게임에 사용할 단어가 입력된다.

출력 설명

승주가 이길 수 있을 경우 "DA"를 출력하고, 그렇지 못할 경우 "NE"를 출력한다.
그 다음 줄에는 승주가 만들 수 있는 사전 순으로 가장 빠른 단어를 출력한다.

입력 예시 Copy

2
ne

출력 예시 Copy

NE
n

도움

Sample Input 2

4
kava

Sample Output 2

DA
ak

Sample Input 3

8
cokolada

Sample Output 3

DA
acko

출처/분류