백준 #1141 접두사

이번 문제는 접두사문제입니다.  문제의 뜻을 잘 해석 해야 하는데, 접두사 X 집합이라는 뜻을 잘 이해하셔야 합니다.  난이도는 Silver I이며, 정답률은 44.6% 정도입니다.  난이도는 보통이면서 예외가 많지 않은 편입니다.

 

prefix and suffix

 

문제 링크입니다.

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

1141번: 접두사

이 문제는  prefix 종속성이 있는 집합을 정하고, 집합의 수가 얼마가 될 것인가를 알아보는 것입니다.  예를 들어서 { baekjoon, banana, ba, baek, ban } 라는 문자열 집합이 있다고 하죠.  종속성이 있는 집합을 나누어보면, {baekjoon, ba, baek} 와 {banana, ba, ban} 으로 나눌 수 있습니다.  같은 집합에서 두개의 원소를 선택하면, 종속관계가 있어서, 접두사X 집합이 될 수 없습니다.  즉, {baekjoon, baek, ban}은 접두사X 집합이 아니게 된 것이죠.  그러면, 각 집합에서 하나씩 골라서 집합을 만들어야 합니다.  {ba, ban} 과 같이 교집합에 있는 원소를 고르면 안 되겠죠.  가장 편한 것은 가장 길이가 큰 원소들을 고르는 것입니다.  {baekjoon, banana}를 고르면 접두사X 집합이 됩니다.  또는 차집합중 하나씩 선택하든, 사실 이것은 문제를 푸는데 중요한 것은 아닙니다.  최대 접두사X 집합을 만들려면, 각각의 접두사 종속 집합에서 하나씩 빼와야 한다는 것입니다.

 

이것을 기초로 해서 알고리즘을 작성하면 됩니다.  전 정렬을 한번 해서, 길이가 긴 것부터 차례로 앞에 있는 원소들과 비교를 했습니다.  알고리즘 복잡도는 \(O(N^2 L) 입니다.  N의 최댓값이 50이고, 문자열 길이의 최댓값이 50이니까, 많아보았자 125,000 정도의 숫자입니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1141 - Prefix
//    - by Aubrey Choi
//    - created at 2020-01-05
//----------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <algorithm>

struct Node { int n; char *p; } v[50];
bool cmp(Node &a, Node &b) { return a.n>b.n; }
int main()
{
  char s[50][52];
  int n, i, j, cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    scanf("%s", s[i]);
    v[i].n=strlen(s[i]);
    v[i].p=s[i];
  }
  std::sort(v,v+n,cmp);
  for(i=1;i<n;i++) for(j=0;j<i;j++)
  {
    if(v[j].n&&!strncmp(v[j].p,v[i].p,v[i].n))
    {
      cnt++;
      v[i].n=0;
      break;
    }
  }
  printf("%d\n", n-cnt);
}