염라대왕은 이승의 사람들의 모든 이름을 가지고 있다.

어느날 저승에 일어난 진도 8.0 지진에 항상 정리되어 있던 이승 명부가 흐트러졌다.

이승 명부는 이름의 길이가 짧을수록 이 앞에 있었고, 같은 길이면 사전 순으로 앞에 있었다.

이왕 이렇게 된 김에 모든 이름을 다시 정리하고 같은 이름은 하나만 남겨놓기로 한 염라대왕을 도와주자.

[입력]

첫 번째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 50)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 이승 명부의 이름 개수 N(1 ≤ N ≤ 20,000)이 주어진다.

각 테스트 케이스의 두 번째 줄부터 N개의 줄에 걸쳐서 알파벳 소문자로 이루어진 이름들이 주어진다.

이름에는 공백이 포함되지 않으며 최소 1개, 최대 50개의 알파벳으로 이루어져 있다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

정리된 이름을 한 줄에 하나씩 출력하라. 같은 이름은 한 번만 출력해야 하는 것을 주의하라.

풀이

단순한 정렬문제이다. 나는 Quick Sort 를 배운 참에 써먹어 보기로 결심했다. 정렬코드는 사실 그대로고, 메인함수에서 정렬방식에 대한 방법을 지정해주는 것으로 문제의 요구사항을 충족시킬 수 있었다.

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  freopen("s_input.txt", "r", stdin);

  size_t t;
  cin >> t;
  for (size_t tc = 1; tc <= t; ++tc) {
    cout << "#" << tc << "\\n";

    size_t n;
    cin >> n;
    vector<string> ls;

    for (size_t i = 0; i < n; ++i) {
      string word;
      cin >> word;
      ls.push_back(word);
    }

    sol1::sort(ls.begin(), ls.end(), [](auto a, auto b) {
      if (a.size() == b.size()) {
        // sort by string
        return a < b;
      }
      // sort by length
      return a.size() < b.size();
    });

    // make it unique
    auto end = std::unique(ls.begin(), ls.end());
    std::for_each(ls.begin(), end, [](auto elem) { cout << elem << "\\n"; });
  }

  return 0;
}

문자열의 길이를 우선적으로 정렬하고, 길이가 같으면 일반적인 사전순(Lexicographic order)으로 정렬한다. 위와 같이 정렬의 방식을 알고리즘 밖에서 정의하는 패턴을 전략패턴 Template Method Pattern / Strategy Pattern 이라고 부른다.

마지막으로 같은 단어를 제거하기 위해 std::unique 함수를 사용했다. 얘는 중복되는 원소를 제거하여 줄어든 컨테이너의 마지막 위치를 가리켜준다.