```
백준 5052번 전화번호 목록 C++ 구현해보기
```
이번 글을 통해 배워갈 내용
- 백준 5052번 풀이
- c++ list asc dsc sorting
- c++ find substring from string
- c++ using hashmap
https://www.acmicpc.net/problem/5052
5052번: 전화번호 목록
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가
www.acmicpc.net
백준 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++ 이론을 배울수 있는 곳 정리
개요 C++을 배우는 책, 강의, 블로그, 링크 등을 공유합니다. (링크 및 간략한 설명을 하였으나 만약 원작자가 링크를 거는것을 원치 않을 경우 연락주시기 바랍니다.) 서적 https://www.amazon.com/Prime
codemasterkimc.tistory.com
https://codemasterkimc.tistory.com/50
300년차 개발자의 좋은 코드 5계명 (Clean Code)
이번 글을 통해 배워갈 내용 좋은 코드(Clean Code)를 작성하기 위해 개발자로서 생각해볼 5가지 요소를 알아보겠습니다. 개요 좋은 코드란 무엇일까요? 저는 자원이 한정적인 컴퓨터 세상에서 좋
codemasterkimc.tistory.com
'C++ > C++ 알고리즘' 카테고리의 다른 글
| 백준 1568번 새 C++ 구현해보기 (0) | 2021.10.29 |
|---|---|
| 백준 5522번 카드게임 C++ 구현해보기 (0) | 2021.10.24 |
| 백준 5054번 주차 C++ 구현해보기 (0) | 2021.10.16 |
| 백준 7510번 고급수학 C++ 구현해보기 (0) | 2021.10.14 |
| 백준 5800번 성적통계 C++ 구현해보기 (0) | 2021.10.11 |
```
백준 5052번 전화번호 목록 C++ 구현해보기
```
이번 글을 통해 배워갈 내용
- 백준 5052번 풀이
- c++ list asc dsc sorting
- c++ find substring from string
- c++ using hashmap
https://www.acmicpc.net/problem/5052
5052번: 전화번호 목록
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가
www.acmicpc.net
백준 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++ 이론을 배울수 있는 곳 정리
개요 C++을 배우는 책, 강의, 블로그, 링크 등을 공유합니다. (링크 및 간략한 설명을 하였으나 만약 원작자가 링크를 거는것을 원치 않을 경우 연락주시기 바랍니다.) 서적 https://www.amazon.com/Prime
codemasterkimc.tistory.com
https://codemasterkimc.tistory.com/50
300년차 개발자의 좋은 코드 5계명 (Clean Code)
이번 글을 통해 배워갈 내용 좋은 코드(Clean Code)를 작성하기 위해 개발자로서 생각해볼 5가지 요소를 알아보겠습니다. 개요 좋은 코드란 무엇일까요? 저는 자원이 한정적인 컴퓨터 세상에서 좋
codemasterkimc.tistory.com
'C++ > C++ 알고리즘' 카테고리의 다른 글
| 백준 1568번 새 C++ 구현해보기 (0) | 2021.10.29 |
|---|---|
| 백준 5522번 카드게임 C++ 구현해보기 (0) | 2021.10.24 |
| 백준 5054번 주차 C++ 구현해보기 (0) | 2021.10.16 |
| 백준 7510번 고급수학 C++ 구현해보기 (0) | 2021.10.14 |
| 백준 5800번 성적통계 C++ 구현해보기 (0) | 2021.10.11 |
