문제) 문자열 A가 주어지고, 그것보다 짧은 문자열로 구성된 배열 T가 주어진다. 배열 T에 들어있는 각 문자열이 A의 부분 문자열인지를 검사한다.
물론, C++에서 제공하는 string 클래스의 find 함수를 사용하면 하고 말 것도 없다. 여기에서는 좀 더 효율적이라고 생각되는 방법을 디자인해보는 것이 목표이다.
예를 들어 A가 'apple'이라는 문자열이라고 하자. 이제, T의 임의의 문자열 t가 'apple', 'pple', 'ple', 'le', 'e'의 prefix인지 확인하면 된다. t의 첫 글자가 'a', 'p', 'l', 'e' 중의 하나가 아니라면 더 이상 비교해 볼 필요도 없다. 만일 t의 첫 글자가 'p'이면, 두 번째 글자가 'p' 혹은 'l'인지를 확인한다. A 문자열을 가지고 다음과 같은 N-ary Tree를 그리면 된다. 나의 그래프 표현 방식이 이해가 될지는 모르겠다. 왼쪽에서 오른쪽으로 보면 된다.
A+a-p-p-l-e
+p-p-l-e
| +l-e
+l-e
+e
이진 검색 트리(Binary Search Tree)는 나름 구현하기 쉽지만, N-ary tree는 구현해 본적이 없다. 자식 노드가 여러 개인 것을 어떻게 표현해야 할까 싶다. 노드의 자식 노드에 대한 포인터를 연결 리스트(Linked List) 혹은 배열로 구현해도 될 것 같다. 이번에는 C++에서 제공하는 vector를 사용해보기로 했다.
그런데, 문제가 생겼다. 구조체 내에 vector를 선언하고 계속 데이터를 push_back을 하다 보니 메모리 위치가 중복되는지 segmentation fault가 난다. 해당 node 구조체를 malloc으로 선언할 때 그 구조체 크기보다 훨씬 크게 선언해주면 segmentation fault가 나지 않는다. 문제는 알겠지만, 해결책은 아직 구하지 못했다. 문제가 되는 라인은 32번째 라인이다.
아직 C도 아닌 것이 C++도 아닌 오묘한 코드이다.
/*
Date: 03/18/10
Prob) Check if each word in an array of strings is a substring of a given string.
*/
#include <iostream>
#include <vector>
using namespace std;
typedef struct node {
char ch;
vector<struct node*> child;
} Node, *pNode;
// return the current node's child having ch if exists
pNode findChar(pNode n, char ch) {
for (vector<pNode>::iterator iter=(n->child).begin();
it!=(n->child).end();
++it)
{
if ((*it)->ch == ch)
return *it;
}
return NULL;
}
// insert each character of the given string into N-ary tree (No duplicate)
void insertString(pNode n, string str, int idx) {
pNode fnode = findChar(n, str.at(idx));
if (fnode == NULL) { // not exist
pNode newnode = (pNode)malloc(sizeof(Node)*3); // very poor!!
newnode->ch = str.at(idx);
(n->child).push_back(newnode);
fnode = newnode;
}
if (str.length() > (unsigned)(idx + 1))
insertString(fnode, str, idx+1);
}
void findString(pNode root, string str) {
for (int i = 0; i < str.length(); i++) {
root = findChar(root, str.at(i));
if (root == NULL) {
cout << "'" << str << "' is not a substring." << endl;
return;
}
}
cout << "'" << str << "' is a substring." << endl;
}
int main() {
pNode root = (pNode)malloc(sizeof(Node));
string str = "apple";
string arstr[5] = {"ap", "pl", "app", "kg", "ds"};
cout << "Check if each word is a substring of '" << str << "'." << endl;
for (int i = 0; i < str.length(); i++)
insertString(root, str.substr(i), 0);
for (int i = 0; i < 5; i++)
findString(root, arstr[i]);
return 0;
}
two strings, s1 and s2, write a program to check if s1 is a rotation of s2. But you can use strstr() only once. (abcdef = cdefab)
간단해 보이는데 방법이 잘 떠오르지 않았다. 침대에 엎드려서 생각해낸 방법으로 열심히 코딩을 한 후 답안을 확인해보니 2줄이면 끝난다.
내가 사용한 방법은 s1의 맨 끝단어(s1[n])와 맨 앞단어(s1[0])를 붙여서 이 문자열(t)이 s2에 존재하는 위치를 먼저 구한다. t가 s2에 존재하면 t가 존재하는 위치 뒷부분, s2의 맨 앞에서 t가 존재하는 부분 직전까지의 문자열이 각각 s1에 존재하는지를 적절하게 체크한다. 다만, t가 s2에 존재하지 않는 경우 중에 s1=s2인 경우가 있으니까 주의하여 체크한다.
s[0]{ A }{ B }s[n] -> { B }s[n]s[0]{ A }
정답에서 사용한 방법은 s1+s1인 문자열을 만들고, s2가 그 안에 존재(strstr)하면 된다. 간단하다. 결과적으로는 s1을 순환하는 문자열로 생각한다는 점은 비슷했는데 내가 쓴 방법은 아주 지저분하고, 정답은 깔끔하다. 문제는 인터뷰를 할 때 나처럼 푼다면 짧은 시간 내에 오류 없이 소스를 완성 시키지 못할 것이 분명하기 때문에 정답과 같은 접근이 반드시 필요하다. 아흥!
#include <stdio.h>
#include <string.h>
bool isRotation(const char *str1, const char *str2) {
int len = strlen(str1);
if (len != strlen(str2))
return false;
char tmp[3];
tmp[0] = str1[len-1];
tmp[1] = str1[0];
tmp[2] = 0;
const char *pos;
if ((pos = strstr(str2, (char*)tmp)) != NULL) {
int lens = strlen(pos+2);
if (strncmp(pos+2, str1+1, lens))
return false;
if (strncmp(str2, str1+lens+1, len-lens-2))
return false;
return true;
} else {
return !strcmp(str1, str2);
}
}
int main() {
char str1[128];
char str2[128];
while(true) {
scanf("%s", &str1);
if (!strcmp(str1, "#"))
break;
scanf("%s", &str2);
if (isRotation(str1, str2))
printf("Rotation\n");
else
printf("Not Rotation\n");
}
return 0;
}
