[백준 25192번 C/C++] 인사성 밝은 곰곰이

 

목차

 

 

---

 

 

[백준 25192번 C/C++]인사성 밝은 곰곰이

 

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

25192번: 인사성 밝은 곰곰이

 

---

 

시도 1 - vector 사용

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;	

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, cnt=0;
	bool flag;
	cin>>n;
	
	string input;
	vector<string> v;
	
	for(int i=0; i<n; i++){
		cin>>input;
		flag=false;
		
		if(input=="ENTER")
		{
			v.clear();
		}
		else
		{
			for(int i=0; i<v.size(); i++)
			{
				if(input==v[i]) flag=true; continue;
			}
			
			if(flag==false)
			{
				v.push_back(input);
				cnt++;
			}
		}
	}

	cout<<cnt;
	
	return 0;
}

 

vector를 사용하여 풀었더니 시간초과가 나왔다.

 

---

 

해결방안

 

더 빠른 실행속도를 위해 vector를 set으로 바꾸어 풀었다. 이 문제에서는 key값이 필요없기 때문에 map보다는 set으로 푸는것이 더 낫다. (나중에 확인해보니 set보다 unordered_set을 사용하면 실행속도가 더 빠르단걸 알았다. unordered_set은 미처 생각하지 못했다.)

 

input과 같은 문자열이 set 내에 있는지 찾을 때 

if( s.find(input) == true )로 시도했다가 컴파일 에러가 났다.

set의 find함수를 사용할 때는 iterator를 사용하자.

 

//set 내의 값 검색 방법
set<string>::iterator it = s.find(input);
if( it != s.end() )

 

---

 

코드

 

#include<iostream>
#include<string>
#include<set>
using namespace std;	

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, cnt=0;
	cin>>n;
	
	string input;
	set<string> s;
		
	for(int i=0; i<n; i++){
		cin>>input;
		
		if(input=="ENTER")
		{
			s.clear();
		}
		else
		{
			set<string>::iterator it = s.find(input);
			if(it !=s.end()) continue; //s내에 입력값 input과 같은 문자열이 있는지 검색
			else
			{
				s.insert(input);
				cnt++;
			}
		}
	}

	cout<<cnt;
	
	return 0;
}

 

 

---