[백준 28064] 이민희진 (C#, C++) - soo:bak

문제 링크

28064번 - 이민희진

설명

n개의 이름이 주어질 때, 연결 가능한 이름 쌍의 개수를 구하는 문제입니다.

두 이름은 한쪽의 접두사와 다른 쪽의 접미사가 같을 때 연결할 수 있습니다.

접근법

모든 쌍에 대해 길이 1부터 두 이름 중 짧은 길이까지 확인합니다.

한쪽의 앞부분이 다른 쪽의 뒷부분과 같으면 연결 가능합니다.

조건을 만족하는 쌍의 개수를 세어 출력합니다.

---

Code

C#

using System;

class Program {
  static bool CanConnect(string a, string b) {
    var m = Math.Min(a.Length, b.Length);
    for (var k = 1; k <= m; k++) {
      if (a.StartsWith(b[^k..]) || b.StartsWith(a[^k..])) return true;
      if (a.EndsWith(b[..k]) || b.EndsWith(a[..k])) return true;
    }
    return false;
  }

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var s = new string[n];
    for (var i = 0; i < n; i++) s[i] = Console.ReadLine()!;

    var ans = 0;
    for (var i = 0; i < n; i++) {
      for (var j = i + 1; j < n; j++) {
        if (CanConnect(s[i], s[j])) ans++;
      }
    }
    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<string> vs;

bool canConnect(const string& a, const string& b) {
  int m = min(a.size(), b.size());
  for (int k = 1; k <= m; k++) {
    if (equal(a.begin(), a.begin() + k, b.end() - k)) return true;
    if (equal(b.begin(), b.begin() + k, a.end() - k)) return true;
  }
  return false;
}

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

  int n; cin >> n;
  vs v(n);
  for (int i = 0; i < n; i++) cin >> v[i];

  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (canConnect(v[i], v[j])) ++ans;
    }
  }
  cout << ans << "\n";

  return 0;
}