[Baekjoon] 25192번: 인사성 밝은 곰곰이

 

 

 

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

25192번: 인사성 밝은 곰곰이

 

---

 

문제 해결 과정

착안

동일한 값을 가지는 요소를 중복하여 저장하지 않고 한 번만 저장하는 STL의 컨테이너를 사용하여 닉네임 문자열을 저장한 다음, ENTER 문자열이 입력되기 직전 또는 프로그램 종료 직전까지 컨테이너에 들어온 요소 수를 출력하고자 했다. ENTER 문자열이 입력된 뒤에는 컨테이너를 초기화하여 처음부터 다시 요소 수를 계산하고자 하였다.

 

구현

처음엔 별 생각 없이 STL 컨테이너 중 std::set<> 클래스를 활용하여 문제를 해결했는데, std::set<> 클래스의 경우에는 들어오는 요소들을 키 값에 따라 정렬하는 특징이 있다. 이 때문에 요소의 수가 커질수록 요소를 삽입하는 데에 오랜 시간이 걸리므로, 시간을 단축하기 위해 비슷한 컨테이너인 std::unordered_set<> 클래스를 이용하였다. 사용하고자 하는 자료형이 std::string이므로, std::unordered_set<>을 사용하기 위한 해시 함수나 비교 조건은 디폴트로 사용하였다.

* 참고1) std::set<>: 레드-블랙 트리(red-black tree) 기반으로 작동.

* 참고2) std::unordered_set<>: 해시(hash) 기반으로 작동.

 

한편, ENTER 문자열이 입력되었을 때 컨테이너를 비우는 동작을 구현할 때, std::unordered_set<> 클래스는 컨테이너를 비우는 clear() 메서드의 작동이 요소의 수에 비례하기 때문에 빈 컨테이너를 만들고 swap() 메서드를 사용하여 교체하도록 하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, Count = 0;
	cin >> N;

	unordered_set<string> gomgom;
	string str;
	while (N--)
	{
		cin >> str;
		if (str == "ENTER")
		{
			Count += gomgom.size();
			unordered_set<string>().swap(gomgom);
			continue;
		}

		gomgom.emplace(str);
	}

	Count += gomgom.size();
	cout << Count << "\n";
	return 0;
}

 

실행 결과

 

문제는 금방 해결했지만 더 좋은 결과를 얻기 위해 std::unordered_set<> 클래스를 활용하는 과정에서 별도로 공부해야 할 것들이 많았다. STL 컨테이너들에 대한 이해를 어느 정도 쌓은 줄 알았는데 실전에서 자유자재로 활용하려면, 디테일한 부분에서 STL 컨테이너에 대해 좀 더 공부할 부분이 아직 많은 것 같다.