[2] 카드단어

[시간제한]
50 개의 테스트 케이스를 합쳐 1초.

[메모리제한]
512MB

[문제]

N장의 카드가 놓여져 있는데, 이를 순서대로 선택하여 단어를 만들려고 한다. 단어를 만들 때는 선택한 카드를 이미 선택된 카드들의 제일 왼쪽 또는 오른쪽에만 위치시킬 수 있다.

예를 들어 3장의 카드가 E, O, T 순으로 놓여져 있다고 하자. 순서대로 선택하므로 E를 먼저 선택하고 두번째 O를 E의 왼쪽에 붙일 경우 OE, E의 오른쪽에 붙일 경우 EO가 된다. 세번째 T를 OE의 왼쪽에 붙일 경우 TOE, OE의 오른쪽에 붙일 경우 OET, EO의 왼쪽에 붙일 경우 TEO, EO의 오른쪽에 붙일 경우 EOT라는 단어를 만들 수 있다. 3장의 카드로 만들어진 단어 TOE, OET, TEO, EOT 중에서 사전순으로 가장 느린 단어는 TOE가 된다.

대문자 알파벳이 적힌 N장의 카드가 순서대로 주어질 때, 만들 수 있는 단어 중 가장 사전순으로 느린 단어를 출력하는 프로그램을 작성하시오.

[제한조건]

카드의 수 : N

완성된 단어는 띄어쓰기 없이 붙어있는 형태이다.

한 장의 카드에는 대문자 알파벳 1자가 적혀있다.

• 1 ≤ N ≤ 1000

[입력]

맨 처음 테스트 케이스의 개수 T가 주어지며, 그 다음 줄부터 T 개의 테스트 케이스가 주어진다. 각 테스트 케이스 첫 줄에는 카드의 수 N이 주어진다. 두번째 줄에는 대문자 알파벳이 적힌 N장의 카드가 순서대로 공백으로 구분되어 주어진다.

[출력]

각각의 테스트 케이스에 대하여 #x (x는 테스트 케이스 번호, 1부터 시작)을 출력하고 공백을 하나 둔 다음, N장의 카드로 만들 수 있는 단어 중 가장 사전순으로 느린 단어를 출력한다.

[입출력 예]

(입력)

5  
3  
E O T  
7  
J S M F G S Z   
7  
I H G Y Q D D   
7  
S Z B D A Q T   
10  
D Q Q V L W K G G I  

(출력)

#1 TOE  
#2 ZSSJMFG   
#3 YIHGQDD  
#4 ZSBDAQT  
#5 WVQQDLKGGI

==========================================================================================

[Idea]

*사용한 개념

- Deque (Doubled Ended Queue)

: 카드를 앞과 뒤에 삽입하여 문자열을 완성하기 위해 front와 back에 모두 삽입이 가능한 Deque를 사용했다.

- char * strcmp(const char * str1, const char * str2)

: 대소비교는 해당 문자열의 ASCI값을 토대로 대소비교 판별

: str1 > str2 일 경우 => 0보다 큰 값 return

: str1 < str2 일 경우 => 0보다 작은 값 return

: str1 == str2 일 경우 => 0 return

- Recursion(재귀함수)

: 각 step(문자열을 집어넣는 행동)을 함수로 만들어 재귀함수로 만들었고, 해당 카드의 수가 완료되면 그때 대소비교를 진행했다.

==> Recursion 형태로 진행하면 결론적으로 n개의 카드가 있을 시, 2^(n-1) 개의 경우의 수가 나온다. 

==> 그렇게 완성을 하고 답을 돌려보니 시간초과(TLE)가 떴다. 뭐지... 싶었는데... 2^(n-1)개를 다 하는 게 시간이 오바되는 것 같아서 위의 이미지를 보면 트리의 구조로 나와있다. 그래서 각 step마다 그때그때 비교를 해서 각각 문자를 push_front(), push_back()한 문자열을 비교해서 값이 작은 것(사전순서가 앞인 것)은 재귀함수를 호출하지 않고 큰 것만 재귀함수를 돌리니 결과는 통과!!! 이게 keypoint였던 것 같다. 

[Codes]

[References]

*deque

http://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS3942847236

http://tenlie10.tistory.com/120

*strcmp

http://jink1982.tistory.com/161