백준 5052번 전화번호 목록 C++ 구현해보기

---

```

백준 5052번 전화번호 목록 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 5052번 풀이
2.  c++ list asc dsc sorting
3.  c++ find substring from string
4.  c++ using hashmap

---

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

5052번: 전화번호 목록

 

 

 

백준 5052번은

난이도 골드 등급의 문제로서

 

전화번호 목록이 주어질 때

일관성이 있는지 없는지 판별하는 문제이다.

 

테스트 케이스만큼

전화번호 개수

개수만큼 전화번호가 주어지고

각 테스트 케이스 별로 일관적인지 일관적이지 않은지 판단해서

YES NO를 출력하면 된다.

 

일관성 판단 기준은

각 전화번호가 앞자리에서 해당 전화번호를 포함하는지 확인해주면 된다.

 

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

일단 전화번호를 저장하는 CPhoneNumList클래스를 만들고

class CPhoneNumList
{
private:
	std::list<std::string>phonNumList;
public:
	CPhoneNumList(std::list<std::string> phonNumVec)
	{
		this->phonNumList = phonNumVec;
	}

	const std::list<std::string> getPhoneNumVec()
	{
		return phonNumList;
	}
};

 

전화번호를 판별해주는 CPhoneNumListVerification 클래스를 만들었습니다.

class CPhoneNumListVerification
{
private:
	int32_t testCaseNum;
	std::vector<CPhoneNumList> phoneNumListVec;


public:
	CPhoneNumListVerification();
	~CPhoneNumListVerification();
	void getUserInputTestCase();
	void getUserInputPhoneNumList();
	void printIsConsistent();
};

int main()
{
	CPhoneNumListVerification cPhoneNumListVerification = CPhoneNumListVerification();
	cPhoneNumListVerification.getUserInputTestCase();
	cPhoneNumListVerification.getUserInputPhoneNumList();
	cPhoneNumListVerification.printIsConsistent();
}

 

각 CPhoneNumList들은 CPhoneNumListVerification클래스에서 벡터 안에

std::vector<CPhoneNumList> phoneNumListVec;

와 같이 담어주었고

 

항상 그렇듯

객체 생성해주고

테스트 케이스를 입력받고

테스트 케이스만큼 입력을 받주었고

 

다른 점은

getUserInputPhoneNumList()함수내부에서 다음과 같이

 

void CPhoneNumListVerification::getUserInputPhoneNumList()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);
	for (int32_t i = 0; i < testCaseNum; i++)
	{
		std::string inputStr;
		std::getline(std::cin, inputStr);
		int32_t phoneNumCnt;
		std::istringstream(inputStr) >> phoneNumCnt;

		std::list<std::string> phonNumList;
		for (int32_t i = 0; i < phoneNumCnt; i++)
		{
			std::getline(std::cin, inputStr);
			phonNumList.push_back(inputStr);
		}

		/* Dsc sorting 내림차순 정렬*/
		phonNumList.sort([](const std::string& lhs, const std::string& rhs)->bool {
			return lhs.size() > rhs.size();
			});

		CPhoneNumList cPhoneNumList = { phonNumList };
		phoneNumListVec.push_back(cPhoneNumList);
	}
}

리스트를 받아서 내림차순으로 정렬한 부분입니다.

(c++ list asc dsc sorting)

		/* Dsc sorting 내림차순 정렬*/
		phonNumList.sort([](const std::string& lhs, const std::string& rhs)->bool {
			return lhs.size() > rhs.size();
			});

 

이 문제의 핵심 내용은 결과를 출력하는 CPhoneNumListVerification::printIsConsistent() 함수이고

원래는 함수를 쪼개야 하나 시간 관계상 묶어서 작업했습니다.

 

void CPhoneNumListVerification::printIsConsistent()
{
	for (auto phoneNumListVecIter : phoneNumListVec)
	{
		/* 해쉬맵 선언 */
		std::unordered_map<std::string, bool> consistentMap;

		/* consistency 판별 bool*/
		bool isConsistent = true;

		for (auto phoneNumListsIter : phoneNumListVecIter.getPhoneNumVec())
		{
			if (consistentMap[phoneNumListsIter] == true)
			{
				/*inconsistent*/
				isConsistent = false;
				break;
			}

			/* substring find*/
			int phoneNumListsIterLen = phoneNumListsIter.length();
			//for (int idx1 = 0; idx1 < phoneNumListsIterLen; idx1++) {
			int idx1 = 0;
				for (int idx2 = idx1; idx2 < phoneNumListsIterLen; idx2++) {
					std::string tempStr = "";
					for (int idx3 = idx1; idx3 <= idx2; idx3++) {
						tempStr += phoneNumListsIter[idx3];
					}
					//std::cout << tempStr << " ";
					consistentMap[tempStr] = true;
				}
			//}
			//std::cout << "\n";
		}

		std::cout << (isConsistent ? "YES" : "NO") << "\n";

	}

}

 

해쉬 맵을 만들어서 해쉬 맵에 있으면 일관성이 없다로 판별하고

(c++ using hashmap)

		/* 해쉬맵 선언 */
		std::unordered_map<std::string, bool> consistentMap;
        
        // 기타 코드
        
   		if (consistentMap[phoneNumListsIter] == true)
		{
			/*inconsistent*/
			isConsistent = false;
			break;
		}
        
        // 기타 코드

 

 

없으면 substring을 찾아줍니다.

			/* substring find*/
			int phoneNumListsIterLen = phoneNumListsIter.length();
			//for (int idx1 = 0; idx1 < phoneNumListsIterLen; idx1++) {
			int idx1 = 0;
				for (int idx2 = idx1; idx2 < phoneNumListsIterLen; idx2++) {
					std::string tempStr = "";
					for (int idx3 = idx1; idx3 <= idx2; idx3++) {
						tempStr += phoneNumListsIter[idx3];
					}
					//std::cout << tempStr << " ";
					consistentMap[tempStr] = true;
				}
			//}
			//std::cout << "\n";

이때 주의할 점이

substring 전체가 아니고 앞자리에서 시작하는 것 만 찾는 것이기 때문에 위와 같이 전체 찾는 부분을 주석처리하였고

 

앞에서 시작하는 게 아닌 전체를 찾고자 한다면

아래 코드를 참조하시면 좋을 듯합니다.

			/* substring find*/
			int phoneNumListsIterLen = phoneNumListsIter.length();
			for (int idx1 = 0; idx1 < phoneNumListsIterLen; idx1++) {
			int idx1 = 0;
				for (int idx2 = idx1; idx2 < phoneNumListsIterLen; idx2++) {
					std::string tempStr = "";
					for (int idx3 = idx1; idx3 <= idx2; idx3++) {
						tempStr += phoneNumListsIter[idx3];
					}
					std::cout << tempStr << " ";
					consistentMap[tempStr] = true;
				}
			}
			std::cout << "\n";

 

요즘 함수 지향적으로 생각을 하려고 노력하다 보니 코드가 길어지네요 ㅎㅎ

 

전체 코드는 다음과 같습니다

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>


class CPhoneNumList
{
private:
	std::list<std::string>phonNumList;
public:
	CPhoneNumList(std::list<std::string> phonNumVec)
	{
		this->phonNumList = phonNumVec;
	}

	const std::list<std::string> getPhoneNumVec()
	{
		return phonNumList;
	}
};


class CPhoneNumListVerification
{
private:
	int32_t testCaseNum;
	std::vector<CPhoneNumList> phoneNumListVec;


public:
	CPhoneNumListVerification();
	~CPhoneNumListVerification();
	void getUserInputTestCase();
	void getUserInputPhoneNumList();
	void printIsConsistent();
};

int main()
{
	CPhoneNumListVerification cPhoneNumListVerification = CPhoneNumListVerification();
	cPhoneNumListVerification.getUserInputTestCase();
	cPhoneNumListVerification.getUserInputPhoneNumList();
	cPhoneNumListVerification.printIsConsistent();
}

CPhoneNumListVerification::CPhoneNumListVerification()
{
	testCaseNum = 0;
}

CPhoneNumListVerification::~CPhoneNumListVerification()
{
}


void CPhoneNumListVerification::getUserInputTestCase()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);
	std::string inputStr;
	std::getline(std::cin, inputStr);
	std::stringstream ss(inputStr);
	ss >> testCaseNum;
}

void CPhoneNumListVerification::getUserInputPhoneNumList()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);
	for (int32_t i = 0; i < testCaseNum; i++)
	{
		std::string inputStr;
		std::getline(std::cin, inputStr);
		int32_t phoneNumCnt;
		std::istringstream(inputStr) >> phoneNumCnt;

		std::list<std::string> phonNumList;
		for (int32_t i = 0; i < phoneNumCnt; i++)
		{
			std::getline(std::cin, inputStr);
			phonNumList.push_back(inputStr);
		}

		/* Dsc sorting 내림차순 정렬*/
		phonNumList.sort([](const std::string& lhs, const std::string& rhs)->bool {
			return lhs.size() > rhs.size();
			});

		CPhoneNumList cPhoneNumList = { phonNumList };
		phoneNumListVec.push_back(cPhoneNumList);
	}
}

void CPhoneNumListVerification::printIsConsistent()
{
	for (auto phoneNumListVecIter : phoneNumListVec)
	{
		/* 해쉬맵 선언 */
		std::unordered_map<std::string, bool> consistentMap;

		/* consistency 판별 bool*/
		bool isConsistent = true;

		for (auto phoneNumListsIter : phoneNumListVecIter.getPhoneNumVec())
		{
			if (consistentMap[phoneNumListsIter] == true)
			{
				/*inconsistent*/
				isConsistent = false;
				break;
			}

			/* substring find*/
			int phoneNumListsIterLen = phoneNumListsIter.length();
			//for (int idx1 = 0; idx1 < phoneNumListsIterLen; idx1++) {
			int idx1 = 0;
				for (int idx2 = idx1; idx2 < phoneNumListsIterLen; idx2++) {
					std::string tempStr = "";
					for (int idx3 = idx1; idx3 <= idx2; idx3++) {
						tempStr += phoneNumListsIter[idx3];
					}
					//std::cout << tempStr << " ";
					consistentMap[tempStr] = true;
				}
			//}
			//std::cout << "\n";
		}

		std::cout << (isConsistent ? "YES" : "NO") << "\n";

	}

}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---