[11313번] Best Buddies

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Map STL :: http://www.crocus.co.kr/604

이 문제는 맵으로 해결이 가능하다.

우선 두 사람의 이름을 문제에 맞게 받아오고 (str2, str1)순으로 맵에 넣어준다.

그리고 난 뒤 넘버링을 해주게 되는데 넘버링을 하는 이유는 하나의 그룹에서 그 사람이 몇번째에 위치하는지 알기 위해서이다.

예를들어 ㅁㅁㅁ가 하나의 그룹일 때 ㅁㅁㅁ인지 ㅁㅁㅁ인지 ㅁㅁㅁ인지 확인하기 위함이다.

쿼리를 받고 마지막으로 그 해당하는 사람의 인덱스를 파악하여 %3 나머지 연산을 통해 문제를 해결하면 쉽게 문제를 풀 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <vector>
 
using namespace std;
 
typedef pair<string, string> pss;
 
map<pss, int> mp;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        char str1[30], str2[30];
        scanf("%s %s", str1, str2);
 
        mp[{str2, str1}] = 1;
    }
 
    // 다시 넘버링(인덱스 파악용)
    int num = 1;
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        it->second = num;
        num++;
    }
 
    int q;
    scanf("%d", &q);
 
    while (q--)
    {
        char str1[30], str2[30];
        scanf("%s %s", str1, str2);
 
        // 인덱스 파악
        int idx = mp[{str2, str1}];
 
        // 인덱스가 3으로 나눌때 0이 남으면 
        // 즉, A B C가 하나의 친구 그룹으로 나열될 때 A에 사람이 있다면
        if (idx % 3 == 0)
        {
            auto it = mp.lower_bound({ str2, str1 });
            it--;
            it--;
 
            printf("%s %s\n", it->first.second.c_str(), it->first.first.c_str());
            it++;
 
            printf("%s %s\n", it->first.second.c_str(), it->first.first.c_str());
            it++;
        }
 
        // 인덱스가 3으로 나눌때 2가 남으면 
        // 즉, A B C가 하나의 친구 그룹으로 나열될 때 C에 사람이 있다면
        else if (idx % 3 == 2)
        {
            auto it = mp.lower_bound({ str2, str1 });
            it--;
 
            printf("%s %s\n", it->first.second.c_str(), it->first.first.c_str());
            it++;
            it++;
 
            printf("%s %s\n", it->first.second.c_str(), it->first.first.c_str());
        }
        // 인덱스가 3으로 나눌때 1이 남으면 
        // 즉, A B C가 하나의 친구 그룹으로 나열될 때 B에 사람이 있다면
        else if (idx % 3 == 1)
        {
            auto it = mp.lower_bound({ str2, str1 });
 
            it++;
            printf("%s %s\n", it->first.second.c_str(), it->first.first.c_str());
 
            it++;
            printf("%s %s\n", it->first.second.c_str(), it->first.first.c_str());
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>