[백준][C++] 5052번 전화번호 목록

5052번 전화번호 목록

문제 링크

전화번호 목록

분석

전화번호 목록이 주어지고, 어떤 번호가 다른 번호의 접두어가 되는 경우가 있는지 판단하는 문제입니다.

길이가 더 긴 문자열은 짧은 문자열의 접두어가 될 수 없습니다.

완전탐색으로 풀면 시간초과가 발생합니다.
정렬이나 트라이 자료구조로 풀이할 수 있습니다.

풀이

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int main()
{
	// 테스트 케이스의 개수
	int t;
	std::cin >> t;

	// 테스트 케이스만큼 반복
	for (int i = 0; i < t; ++i)
	{
		// 각 테스트 케이스의 전화번호 개수
		int n;
		std::cin >> n;

		// 전화번호를 문자열로 저장하는 벡터
		std::vector<std::string> numStr;

		// 전화번호를 문자열로 입력받고, 벡터에 저장하는 반복문
		for (int j = 0; j < n; ++j)
		{
			std::string str;
			std::cin >> str;

			numStr.push_back(str);
		}

		// 전화번호들을 사전순으로 정렬한다.
		std::sort(numStr.begin(), numStr.end());

		// 접두어 관계가 없다는 것으로 가정하고 시작한다.
		bool isValid = true;

		// 정렬된 벡터에서 인접한 두 문자열을 비교하는 반복문
		for (int i = 0; i < numStr.size() - 1; ++i)
		{
			std::string current = numStr[i]; // 현재 문자열
			std::string next = numStr[i + 1]; // 다음 문자열

			// next의 앞 부분 문자열이 current와 같다면 접두어 관계이다.
			if (next.compare(0, current.size(), current) == 0)
			{
				// 접두어 관계이므로 bool 값 수정
				isValid = false;
				// 뒷 부분은 더 이상 확인할 필요가 없다.
				break;
			}
		}

		// 결과 출력
		if (isValid)
		{
			std::cout << "YES" << std::endl;
		}
		else
		{
			std::cout << "NO" << std::endl;
		}
	}
}

전화번호들을 문자열로 저장하고, 정렬합니다.
접두어 관계에 있다면 사전순으로 정렬되기 때문에 정렬 후 인접한 두 문자열 사이에 존재하게 됩니다.
인접한 번호끼리 확인하여 접두어가 되는지 확인합니다.

성능 요약

시간 복잡도는 $O\left( \sum \limits_{i = 1}^{t} n_i \ \log \ n_i \times l \right)$입니다.

• 테스트 케이스만큼 반복 $O(t)$
• 전화번호를 문자열로 입력받고, 벡터에 저장하는 반복문 $O(n)$
• 정렬 $O(n \ log \ n)$
• 인접한 두 문자열 비교 $O(n \times l)$
  • l은 문자열의 길이
• $O(t) \times (O(n) + O(n \ log \ n) + O(n \times l)) \approx O(t \times n \ log \ n \times l)$

공간 복잡도는 $O(n \times l)$입니다.

• 전화번호를 문자열로 저장하는 벡터 std::vector<std::string> numStr $O(n \times l)$

메모리: 3064 KB

시간: 112 ms