C++ / 백준 / 5052 / 전화번호 목록

문제

 

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

문제풀이

 

프로그래머스 문제와 똑같은 문제이다. (https://school.programmers.co.kr/learn/courses/30/lessons/42577)

한 번호가 다른 번호의 접두어인 경우가 있는지를 구하는 문제이다.

 

긴 번호는 짧은 번호의 접두어가 될 수 없으므로 길이의 오름차순으로 정렬을 한다.

 

번호를 맨 왼쪽부터 오른쪽으로 가면서 번호를 합친다.

그리고 unordered_set인 list에서 해당 번호를 찾아본다.

있다면 일관성이 없는 경우이므로 종료하고 NO를 출력하면 된다.

없어서 반복문이 종료되면 unordered_set인 list에 해당 번호를 저장한다.

 

코드

#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;

bool cmp(const string& l1,const string& l2) {
	return l1.size() < l2.size();
}

int main() {
	int T(0);
	cin >> T;
	for (int test_case = 1; test_case <= T; ++test_case) {
		int N(0);
		cin >> N;
		
		vector<string>list(N, "");
		for (int idx = 0; idx < N; ++idx) {
			cin >> list[idx];
		}

		sort(list.begin(), list.end(), cmp);

		unordered_set<string>set_list;		
		string answer("YES");
		for (int idx = 0; idx < N; ++idx) {
			string number("");
			for (int num_idx = 0; num_idx < list[idx].size(); ++num_idx) {
				number += list[idx][num_idx];				
				if (set_list.find(number) != set_list.end()) {
					answer = "NO";
					break;
				}
			}
			if (answer == "NO") break;
			set_list.insert(list[idx]);
		}
		cout << answer <<'\n';
	}
}