[BOJ/백준][Gold4] 2002 : 추월 (C++)

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

2002번: 추월

 

[난이도] Gold4
[유형] 구현

[풀이]
터널 통과전 각 자동차에 대해 자신보다 앞에 가고 있는 자동차를 적절한 자료구조에 기록해놓고
터널 통과후 앞에 이전에 있던 차가 없으면 그 차는 추월을 한것이다.
string 자체로 기록하기 위해 map,set 등을 이용하였는데 index로 변환하여 풀면
메모리 및 시간을 줄일 수 있다.

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2002.cpp

 

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
string a[1001];
int main(){
    ios_base::sync_with_stdio();
    cin.tie();
    map<string,vector<string>> start;
    map<string,set<string>> end;
    int N;
    cin>>N;
    for(int i=N-1;i>=0;i--) cin>>a[i];
    for(int i=0;i<N-1;i++)
        for(int j=i+1;j<N;j++) start[a[i]].push_back(a[j]);
    
    for(int i=N-1;i>=0;i--) cin>>a[i];
    for(int i=0;i<N-1;i++)
        for(int j=i+1;j<N;j++) end[a[i]].insert(a[j]);
    
    int ans = 0;
    for(auto k : start){
        string n = k.first;
        for(auto e : k.second){
            if(end[n].find(e) == end[n].end()) {
                ans++;
                break;
            }
        }
    }
    cout << ans;
}

#include <iostream>
	#include <string>
	#include <vector>
	#include <map>
	#include <set>
	using namespace std;
	string a[1001];
	int main(){
	ios_base::sync_with_stdio();
	cin.tie();
	map<string,vector<string>> start;
	map<string,set<string>> end;
	int N;
	cin>>N;
	for(int i=N-1;i>=0;i--) cin>>a[i];
	for(int i=0;i<N-1;i++)
	for(int j=i+1;j<N;j++) start[a[i]].push_back(a[j]);
	for(int i=N-1;i>=0;i--) cin>>a[i];
	for(int i=0;i<N-1;i++)
	for(int j=i+1;j<N;j++) end[a[i]].insert(a[j]);
	int ans = 0;
	for(auto k : start){
	string n = k.first;
	for(auto e : k.second){
	if(end[n].find(e) == end[n].end()) {
	ans++;
	break;
	}
	}
	}
	cout << ans;
	}