백준 14171 Cities and States (USACO December 2016 Silver 2번)

문제 링크: https://www.acmicpc.net/problem/14171

14171번: Cities and States

city, state의 앞 두 letter들을 네자리수로 만들어서 state들을 기준으로 vector에 입력 받음. 각 도시들을 훑으면서 upper_bound와 lower_bound를 이용하여 special pair의 갯수를 세면 됨.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e3;
 
vector<int> v[MAX];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        string ct, st;
        cin >> ct >> st;
        int c = 100 * (ct[0] - 'A') + ct[1] - 'A';
        int s = 100 * (st[0] - 'A') + st[1] - 'A';
        v[s].push_back(c);
    }
    for(int i = 0; i < MAX; i++)
        sort(v[i].begin(), v[i].end());
 
    int ans = 0;
    for(int i = 0; i < MAX; i++) {
        for(int j = 0; j < v[i].size(); j++) {
            if(i == v[i][j]) continue;
            ans += upper_bound(v[v[i][j]].begin(), v[v[i][j]].end(), i) - lower_bound(v[v[i][j]].begin(), v[v[i][j]].end(), i);
        }
    }
 
    cout << ans / 2 << '\n';
    return 0;
}
 

map을 이용하면 더욱더 간단하게 구현이 가능함.

#include <bits/stdc++.h>
using namespace std;
 
map<pair<string, string>, int> mp;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        string c, s;
        cin >> c >> s;
        c = c.substr(0, 2);
        if(s == c) continue;
        mp[{s, c}]++;
        ans += mp[{c, s}];
    }
 
    cout << ans << '\n';
    return 0;
}