[Baekjoon/C++] 28064번 - 이민희진

[백준] Baekjoon Online Judge

문제로 이동

 

문제

이민희와 민희진을 연결하면 이민희진

김서인과 서인국을 연결하면 김서인국

박건과 건빵을 연결하면 박건빵

민희는 한 사람의 이름 뒷부분이 다른 사람의 이름 앞부분과 같을 때, 이 둘을 연결하는 것을 재밌어한다.

 N명의 사람이 주어질 때, 연결할 수 있는 서로 다른 사람 쌍의 개수를 구해보자.

각각 S, T라는 이름을 가진 두 사람을 연결할 수 있으려면 다음과 같은 조건을 충족해야 한다.

 S, T의 길이보다 작거나 같은 양의 정수 k가 존재하여, S의 앞 k글자와 T의 뒤 k글자가 일치하거나, S의 뒤 k글자와 T의 앞 k글자가 일치해야 한다.

 

입력

첫 줄에는 사람 수 N이 주어진다. (1≤N≤100)

두 번째 줄부터 N개 줄에 걸쳐 각 사람의 이름이 주어진다.

이름은 영어 소문자로만 구성되어 있으며, 길이는 최소 1자, 최대 20자이다.

단, 동명이인이 있을 수 있다.

 

출력

첫 줄에 연결할 수 있는 서로 다른 사람 쌍의 개수를 출력한다.

 

---

풀이

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

int N;
string arr[101];

bool canLink(string a, string b);

bool canLink(string a, string b) {
    int idx = min(a.length(), b.length());

    for (int i = 1; i <= idx; i++) {
        if (a.substr(0, i) == b.substr(b.length() - i, i)) return true;
        if (b.substr(0, i) == a.substr(a.length() - i, i)) return true;
    }

    return false;
}

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (canLink(arr[i], arr[j])) cnt++;
        }
    }

    cout << cnt << '\n';

    return 0;
}

 브루트포스 알고리즘으로 모든 문자쌍을 조사하여 연결할 수 있는 쌍의 개수를 구했다.

 

bool canLink(string a, string b) {
    int idx = min(a.length(), b.length());

    for (int i = 1; i <= idx; i++) {
        if (a.substr(0, i) == b.substr(b.length() - i, i)) return true;
        if (b.substr(0, i) == a.substr(a.length() - i, i)) return true;
    }

    return false;
}

 매개변수로 받은 두 문자열이 연결할 수 있는 쌍인지 확인하는 함수이다. a의 앞에서부터 i칸과 b의 뒤에서부터 i칸, b의 앞에서부터 i칸과 a의 뒤에서부터 i칸이 같다면 true를 return한다.