문제

N장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다. 태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다. 가장 처음에 가져온 카드는 자신의 앞에 놓는다. 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 한다.

예를 들어 3장의 카드가 [M, K, U] 순으로 놓여있다고 하자. 태욱이는 먼저 가장 왼쪽에 있는 “M”이 적힌 카드를 가져와서 자신의 앞에 놓는다. 다음으로 남은 카드 중 가장 왼쪽에 있는 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 “UKM”이라는 문자열을 만들 수 있다. 만약 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 가장 오른쪽에 두면 “KMU”라는 문자열을 만들 수 있다. 이때, 태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열은 “KMU”이다.

N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처음에 놓여있는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N장의 카드에 적힌 알파벳의 초기 순서가 주어진다. 가장 왼쪽에 있는 카드에 적혀있는 알파벳부터 순서대로 N개가 공백으로 구분되어 주어진다. 모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자이다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 한 줄에 1개씩 태욱이가 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 출력한다.

예제 입력

3
3
M K U
5
A S D F G
7
B A C A B A C

예제 출력

KMU
ASDFG
AAABCBC

내가 했던 풀이 방법

1. words를 ""로 초기화한 뒤, input[index]의 값을 N에 저장하고, input[index+1]의 값을 공백으로 분할하여 cards에 저장해준다. (여기서 index는 편의상 index/index+1로 작성했으나, 실제로는 해당 줄을 사용할 때마다 index를 1 증가시켜 준다.)
2. cardPush에 초기값을 depth=0, 'front'/'back', ""로 두고, 함수를 실행한다. cardPush는 카드를 앞 또는 뒤에 붙이는 함수이며, depth는 다음으로 가져올 수 있는 카드의 index이자, 현재 만든 문자열의 length이다. 즉, depth가 N이 되면 재귀를 중단한다. 이때 words에 저장된 문자열이 ""이거나, str보다 사전순이 느릴 경우 words를 str로 바꿔준다.
3. depth가 N이 되지 않았을 경우, loc('front' 또는 'back')에 따라 str 앞 또는 뒤에 cards[depth]를 더해준다.
4. str에 다음으로 가져올 card를 앞과 뒤에 각각 붙인 값 중 사전순이 더 빠른 방향으로 cardPush를 호출해준다. (이를 통해 불필요한 연산을 줄일 수 있다.)
5. cardPush가 끝난 뒤, words에 저장된 문자를 answer에 더해준다.
6. 1번-5번을 case 개수만큼 반복해준다.

코드

const fs = require('fs');
const [cases, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let index = 0;
let N = 0;
let cards = [];
let words = '';
let answer = '';
for (let i = 0; i < Number(cases); i++) {
  words = '';
  N = Number(input[index++].trim());
  cards = input[index++].trim().split(' ');
  cardPush(0, 'front', '');
  cardPush(0, 'back', '');
  answer += words + '\n';
}
console.log(answer.trim());

function cardPush(depth, loc, str) {
  if (depth === N) {
    if (words === '' || words > str) {
      words = str;
    }
    return;
  }

  if (loc === 'front') {
    str = cards[depth] + str;
  } else {
    str += cards[depth];
  }

  if (str + cards[depth + 1] < cards[depth + 1] + str) {
    cardPush(depth + 1, 'back', str);
  } else {
    cardPush(depth + 1, 'front', str);
  }
}

회고

deque 구현 연습으로 풀이하려고 했는데 deque를 구현하지 않고도 문자열만으로도 풀이가 가능했다. 처음에 시간초과 오류가 많이 났는데, cardPush를 너무 자주해주는 것 같아서, 줄일 수 있는 방법을 생각해보다 어차피 지금 현재 사전순으로 비교했을 때도 느린 문자열을 굳이 끝까지 연산할 필요가 없겠구나를 생각하고 다음처럼 조건에 따라 front/back을 나눠줬더니 시간초과는 해결됐지만 이유 모를 틀렸습니다... ㅜㅜ 정말 뭐가 잘못된건지 한참을 찾아봐도 잘 모르겠다... 했는데 words가 새로운 케이스가 될 때마다 초기화가 되고 있나? 에휴 안 되고 있었던 것이었다. 호달달달... 그렇게 words를 초기화해주니 얄밉게도 성공했다. 어쩜 예제랑 반례들은 내가 잘못 구현한 것들과 상관없이 항상 정답을 출력하는건지... 남들 다 안 틀리는 부분만 틀리는건지....