[5052] 전화번호 목록

알고리즘 스터디 1주차 주제: 정렬

---

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

---

문제 요약

1. 어떤 한 번호가 다른 번호의 접두사가 되면 일관성이 없는 목록이다.

2. 위의 경우가 없다면 일관성이 있다고 판단한다.

문제 접근

입력된 문자열을 sort() 알고리즘으로 정렬하면 유사한 전화번호끼리 붙게 된다.

일관성이 깨지는 사례 하나만 찾아서 결과를 반환하면 되므로 앞, 뒤 연속으로 붙은 두 번호만 서로 접두사가 되는지 확인하면 된다.

---

문제 풀이

서로 다른 두 문자열이 포함관계에 있는지 확인하는 것이 핵심인데, 두 가지 방법으로 구현해봤습니다.

 

1. string::find 로 구현

한 문자열 안에서 인수로 전달된 문자열이 검색된 첫 번째 위치를 반환하는 함수.

find()는 인수로 전달된 문자열이 검색되지 않았다면 쓰레기 값, string::npos을 반환합니다. 따라서 함수의 반환 값이 npos라면 포함되지 않은 것, npos가 아니라면 포함된 것입니다.

문제에서는 단순한 포함관계가 아닌 접두사인지 검사해야 하므로 find()에서 반환된 index 값이 0인지 확인하는 조건도 넣어줘야 합니다.

void isPrefix(vector<string> &pb) {
	string result = "YES";

	for (int i = 0; i < pb.size() - 1; i++) {
		if (pb[i + 1].find(pb[i]) != string::npos && pb[i + 1].find(pb[i]) == 0) {
			result = "NO";
			break;
		}
	}
	cout << result << '\n';
	
	return;
}

 

2. string::substr 로 구현

파라미터로 시작 위치(pos)와 길이(len)를 전달받아한 문자열의 일부분을 복사해 반환하는 함수.

한 문자열을 (0, 다른 문자열의 길이]까지 잘라 반환된 문자열이 다른 문자열과 같은지 검사합니다.

번호를 0부터 비교할 문자열의 크기만큼 잘라 비교할 번호와 일치하는지 검사하면 prefix인지 알 수 있습니다. 

void isPrefix(vector<string> &pb) {
	string result = "YES";

	for (int i = 0; i < pb.size() - 1; i++) {
		if (pb[i] == pb[i+1].substr(0, pb[i].size())) {
			result = "NO";
			break;
		}
	}
	cout << result << '\n';
	
	return;
}

---

전체 코드

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

using namespace std;

void isPrefix(vector<string> &pb) {
	string result = "YES";

	for (int i = 0; i < pb.size() - 1; i++) {
		if (pb[i + 1].find(pb[i]) != string::npos && pb[i + 1].find(pb[i]) == 0) {
			result = "NO";
			break;
		}
	}
	cout << result << '\n';
	
	return;
}

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

	vector<string> phoneBook;
	int t = 0;
	int n = 0; 

	cin >> t;

	for (int test = 0; test < t; test++) {
		cin >> n;

		for (int i = 0; i < n; i++) {
			string pn;
			cin >> pn;
            
			phoneBook.push_back(pn);
		}
		sort(phoneBook.begin(), phoneBook.end());

		isPrefix(phoneBook);
		phoneBook.clear();
	}

	return 0;
}

---

TMI

풀이 방법이 두 가지가 된 이유는 처음에 find로 구현하면서 조건문을 추가로 넣어야 한다는 생각을 못하고 풀다가 삽질 끝에 다른 방법을 찾았기 때문입니다,,

나중에 머리가 깨끗한 상태로 다시 생각해보니까 조건을 더 넣어줘야겠더라고요.🥲👍

substr이 더 깔끔한 것 같지만 저처럼 find로 구현하다가 막히는 분들이 있을까(과연) 싶어서 풀이 공유합니다.

 

참고자료

https://cplusplus.com/reference/string/string/substr/

https://cplusplus.com/reference/string/string/substr/

https://cplusplus.com/reference/string/string/find/

https://cplusplus.com/reference/string/string/find/