🚀 [NAMING] 문제 😊😊😊😊😊
아주대에 사는 외수는 작명에 능하기로 유명해서 많은 부부들이 아주대로 몰려와서 태어나는 아이들의 이름을 지어달라고 한다. 부부들은 이름은 잘 짓는게 출세에 영향을 미친다고 생각을 하고 있으며, 따라서 좋은 이름을 지어 출세하기를 기원한다. 허나 게으른 외수에게 작명은 지루한 작업이다. 효율적으로 일을 하고자 궁리하던 차에 쉽지만 기가 막힌 알고리즘을 고안하게 되었다.
외수가 개발한 작명 알고리즘은 다음과 같다.
아버지의 이름 뒤에 어머니의 이름을 덧붙여서 하나의 새로운 문자열 S로 만든다.
이 문자열 S의 접두사(prefix)도 되고 접미사(suffix)도 되는 문자열을 찾는다.
예를 들어 아버지의 이름이 ‘ala’고 어머니의 이름이 ‘la’ 일 경우 S = ‘ala’ + ‘la’ = alala다. 그리고 이 문자열의 접두사이기도 하고 접미사이기도 한 문자열은 다음 세가지다.
- a
- ala
- alala
아버지와 어머니의 이름이 주어질 때, 외수의 규칙을 이용해 지어줄 수 있는 이름들을 모두 찾는 프로그램을 작성하라. 문제에서는 편의상 모든 문자열 대신, 가능한 모든 문자열의 길이를 찾는다.
🔑 [풀이]
아버지와 어머니이름을 합쳤을때 접두사도 되고 접미사도 되는 문자열의 길이를 저장하는 getPartialMatch 함수를 구현한다.
구현함 함수에서 pi를 이용해 쉽게 정답을 알 수 있다. 이후 정렬해야합니다.
코드참고
⌨️ 입력
빈칸이 없는 영문 알파벳 소문자로 이뤄진 문자열이 입력이 두 줄 입력된다.
첫 번째 줄은 아버지의 이름이고, 두 번째 줄은 어머니의 이름이다.
두 문자열의 길이를 합쳐서 400,000 자가 넘어가는 입력은 들어오지 않는다.
🖥 출력
외수가 주어질 수 있는 이름들의 길이들을 한 줄에 출력한다.
출력되는 숫자 사이에는 정확히 공백이 하나 포함되어야 하며, 길이는 오름차순으로 출력되어야 한다.
🖱 입력 예제
ababcabababa
bcabab
💻 출력 예제
2 4 9 18
💎 전체 코드는 다음과 같습니다.
//
// NAMING.cpp
// AALGGO
//
// Created by inhyeok on 2021/12/01.
//
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("NAMING.txt");
/*
N에서 자기 자신을 찾으면서 나타나는 부분일치를 이용해
p[]를 구한다.
p[i] = N[..i]의 접미사도 되고, 접두사도 되는 문자열의 최대 길이
*/
vector<int> getPartialMatch(const string& N){
int m = N.size();
vector<int> pi(m,0);
// KMP 로 자기 자신을 찾는다
// N을 N에서 찾는다. begin = 0 이면 자기 자신을 찾아버리니깐 안됨!
int begin =1, matched = 0;
while(begin+matched < m){
if(N[begin+matched] == N[matched]){
matched++;
pi[begin + matched-1] = matched;
}
else{
if(matched == 0){
begin++;
}
else {
begin += matched - pi[matched-1];
matched = pi[matched-1];
}
}
}
return pi;
}
// s 의 접미사도 되고 접두사도 되는 문자열의 길이를 반환한다.
vector<int> getPrefixSuffix(const string& s){
vector<int> ret, pi = getPartialMatch(s);
int k = s.size();
while(k>0){
ret.push_back(k);
k = pi[k-1];
}
return ret;
}
int main(){
string father, mother;
fin >> father >> mother;
string combined = father + mother;
vector<int> ret = getPrefixSuffix(combined);
sort(ret.begin(), ret.end());
for(int i=0; i< ret.size(); i++){
cout << ret[i] << " ";
}
cout << endl;
return 0;
}
Comments