문제 출처

1. 문제설명

  • 문자열로 구성된 번호가 주어진다.

  • 만약 어떤 문자열이 다른 문자열의 접두어가 되면 안된다.

  • 문제 분류
    • Data Structure, String, Tree, Binary Search, Trie


2. 알고리즘 설계

  • Trie 문제이다.
  • insert 함수
    • 배열에 글자를 저장하기 때문에 배열의 칸을 1칸씩 늘리면서 저장하게 된다.
      • 마치 자료구조 heap처럼
    • 만약 현재 삽입중인 문자열을 다 기록했는데, 현재의 포인터와 배열의 크기가 같지 않다면,
      • 현재 입력중인 문자열 전체가 어떤 문자열의 접두어란 뜻
    • 현재 방문 위치를 기록하는 chk 배열을 통해 재방문 방지


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int MX = 10000 * 10 + 5; // 최대 길이가 10인 10000개 문자열 고려
const int ROOT = 1;

int unused = ROOT + 1;
int nxt[MX][10];
bool chk[MX];

int t, n;

int ctoi(char c) { return c - '0'; }

bool insert(string &s) {
	int cur = ROOT;
	for (auto c : s) {
		if (nxt[cur][ctoi(c)] == -1)
			nxt[cur][ctoi(c)] = unused++;
		cur = nxt[cur][ctoi(c)];
		if (chk[cur]) return 0;
	}
	if (cur != unused - 1) return 0;
	return chk[cur] = 1;
}

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

	cin >> t;
	while (t--) {
		fill(chk, chk + MX, 0);
		for (int i = 0; i < MX; i++)
			fill(nxt[i], nxt[i] + 10, -1);
		unused = ROOT + 1;
		bool isvalid = 1;

		cin >> n;
		string s;
		while (n--)
		{
			cin >> s;
			if (!insert(s)) isvalid = 0;
		}

		cout << (isvalid ? "YES" : "NO") << '\n';
	}
}