백준1764번 듣보잡 C++로 구현해보기

---

```

백준1764번 듣보잡 C++로 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 1764번 풀이
2.  맵을 이용한 두 데이터 그룹 비교

 

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

1764번: 듣보잡

 

백준 1764번 나는 듣보잡은

난이도 쉬움 등급의 문제로서

 

테스트케이스 A와 B를 입력 받은 후

(듣도못한 그룹)A 만큼 키를 입력후 

(보도못한 그룹)B 만큼 키를 가지고 A에 키가 존재하는지 찾고

두 그룹에 모두 존재하는 데이터 그룹의 원소 갯수와 원소 스트링을 출력해주면 되는 문제입니다.

---

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

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

---

접근 방법으로는 맵으로 접근하는 방법이 있고 

 

벡터 컨테이너에 대해 이분 검색을 해서 푸는 방법이 있습니다.

 

저는 맵으로 간단하게 접근하였고

 

문제 특성상 500,000개 * 2 의 데이터를 입력 받기 때문에 시간초과를 줄이기 위해

 

코드를 조금 많이 수정했습니다.

 

---

풀이의 경우

 

일단 해당문제의 경우 테스트케이스가 많기 때문에

	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

위에 코드를 메인에 입력해서 입력으로 인한 시간을 줄여주었고

 

 

유저에게 각 테스트 그룹 갯수를 받고

	void getTestCaseInputFromUser()
	{
		/* 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용*/
		std::string inputStr;
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		ss >> NumberOfGroupA;
		ss >> NubmerOfGroupB;
	}

 

A 그룹에 존재하는 원소를 듣보잡 맵에 넣어주고

std::map<std::string, int> GroupNames;

맵에 존재하는 원소는 1을 맵핑했습니다.

 

	void getInputGroupANamesNtimes()
	{
		for (int i = 0; i < NumberOfGroupA; i++)
		{
			getInputGroupANames();
		}
	}


	void getInputGroupANames()
	{
		/* 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용*/
		std::string inputStr;
		std::string keyStr;

		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		ss >> keyStr;

		GroupNames[keyStr] = 1;
	}

그다음 B원소들을 받아주고

A원소에도 있고 B원소에도 있는 원소는 1을 추가로 더해서 2로 만들었습니다.

	void getInputGroupBNamesNtimes()
	{
		for (int i = 0; i < NubmerOfGroupB; i++)
		{
			getInputGroupBNames();
		}
	}

	void getInputGroupBNames()
	{
		/* 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용*/
		std::string inputStr;
		std::getline(std::cin, inputStr);

		if (GroupNames.count(inputStr) > 0)
		{
			GroupNames[inputStr]++;
			NumberOfAB++;
		}
	}

 

그다음 전체 숫자와 맵핑되는 값이 2인 녀석들만 출력해주면 됩니다.

	void printAnswer()
	{
		std::cout << NumberOfAB << "\n";
		for (auto it = begin(GroupNames); it != end(GroupNames); it++)
		{
			if (it->second == 2)
			{
				std::cout << it->first << "\n";
			}
		}
	}

 

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include<numeric>

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


class CNeverSeenOrHeard
{
private:
	
	/* 듣도 못한 사람 그룹 A */
	int NumberOfGroupA;
	/* 보도 못한 사람 그룹 B */
	int NubmerOfGroupB;

	/* 듣보잡 그룹 AB*/
	int NumberOfAB;
	/* 듣보잡 그룹 AB 맵 1이면 A에 등장, 2이면 둘다 등장했다는 의미*/
	std::map<std::string, int> GroupNames;


public:
	CNeverSeenOrHeard()
	{
		NumberOfAB = 0;
	}

	~CNeverSeenOrHeard()
	{

	}

	void getTestCaseInputFromUser()
	{
		/* 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용*/
		std::string inputStr;
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		ss >> NumberOfGroupA;
		ss >> NubmerOfGroupB;
	}

	void getInputGroupANamesNtimes()
	{
		for (int i = 0; i < NumberOfGroupA; i++)
		{
			getInputGroupANames();
		}
	}


	void getInputGroupANames()
	{
		/* 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용*/
		std::string inputStr;
		std::string keyStr;

		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		ss >> keyStr;

		GroupNames[keyStr] = 1;
	}

	void getInputGroupBNamesNtimes()
	{
		for (int i = 0; i < NubmerOfGroupB; i++)
		{
			getInputGroupBNames();
		}
	}

	void getInputGroupBNames()
	{
		/* 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용*/
		std::string inputStr;
		std::getline(std::cin, inputStr);

		if (GroupNames.count(inputStr) > 0)
		{
			GroupNames[inputStr]++;
			NumberOfAB++;
		}
	}

	void printAnswer()
	{
		std::cout << NumberOfAB << "\n";
		for (auto it = begin(GroupNames); it != end(GroupNames); it++)
		{
			if (it->second == 2)
			{
				std::cout << it->first << "\n";
			}
		}
	}

};

int main()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	CNeverSeenOrHeard* cNeverSeenOrHeard = new CNeverSeenOrHeard();

	cNeverSeenOrHeard->getTestCaseInputFromUser();
	cNeverSeenOrHeard->getInputGroupANamesNtimes();
	cNeverSeenOrHeard->getInputGroupBNamesNtimes();
	cNeverSeenOrHeard->printAnswer();
}

 

 

 

 

읽어주셔서 감사합니다

 

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

 

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

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

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

 

https://codemasterkimc.tistory.com/50

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

 

---