Given
two
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을 순환하는 문자열로 생각한다는 점은 비슷했는데 내가 쓴 방법은 아주 지저분하고, 정답은 깔끔하다. 문제는 인터뷰를 할 때 나처럼 푼다면 짧은 시간 내에 오류 없이 소스를 완성 시키지 못할 것이 분명하기 때문에 정답과 같은 접근이 반드시 필요하다. 아흥!

댓글을 달아 주세요

Write a program to extract the longest repeated substring in a given string.

주어진 문자열에서 반복되는 가장 긴 문자열을 추출하자. 문자열의 길이를 n이라고 했을 때 가장 무식한 방법은 모든 가능한 문자열을 다 구해서 반복되는 문자열을 찾고 긴 문자열을 출력하면 된다. 비교 대상인 두 문자열의 시작점을 i, j라고하고 문자열의 길이를 k라고 하고, 비교할 수 있고 문자열을 비교하는 것 또한 k만큼 필요하므로 대략 O(n^4)이 나온다. 어쨌든, 좋지 않다.

이 문제에 접근하기 위해서 사용되는 것이 suffix array라는 것이다. 문자열에서의 각 시작점들의 인덱스를 값(element)으로 가지는 배열을 말한다. 말로 써놓으면 이해하기 어렵고 간단하게 예를 들면 'banana'라는 문자열이 있을 때 'banana'는 0번 인덱스부터 시작한 것이고, 'anana'는 1번 인덱스부터 시작한 것이다. 또한 'na'의 경우 4번 인덱스부터 시작한 것이다. 이러한 0, 1, 4 등의 값을 가지는 배열을 suffix array라고 한다.

a[] = {"banana", "anana", "nana", "ana", "na", "a"}

위와 같은 식으로 값을 가리키는 셈인데, 이것을 정렬하면

a[] = {"a", "ana", "anana", "banana", "na", "nana"}

와 같은 꼴이 된다. 이제 앞뒤 문자열만 비교하면 순서대로 몇 개의 문자가 일치하는지 쉽게 구할 수 있다. 이 경우 "ana"와 "anana"에서 3자리 문자열 "ana"가 가장 긴 반복되는 문자열이 된다. 이제 시간 복잡도는 O(n*nlogn)이 된다. n은 문자열 비교에서, nlogn은 정렬에서 온 수치이다.

소스 코드 상에서는 compare 함수에서 *(char**)a 를 사용하는 부분이 까다로왔다. 포인터에 대해서 좀 알게 되었나 싶었더니 여전히 잘 모르는 것 같다. 좀 더 알아봐야겠다. Programming Pearls에서 보고 감탄했는데, 알고랭이 좀 했다하는 애들은 중학생들도 아는 알고리즘이라는 것을 알고 나니 부끄럽다. -_-;


댓글을 달아 주세요

C는 CS의 기초중에 기초라고 할 수도 있다.
하지만 C만 제대로 다 알아도 사실상 거의 다 안다고 할 수 있다.

컴프 마지막 숙제는 malloc과 free와 거의 동일한 기능을 하는 함수를 만드는 것인데
이게 사실 ANSI C 책에 그대로 나온다는 사실을 나중에 알았다. (누가 공개를 해버려서...)

문득 예전에 사 놓고 책꽂이에 쳐박혀 있던 이 책의 가치가 새삼스럽게 느껴진다.
책을 얼추 훑어보니 각종 기초 라이브러리에 대한 설명 및 구현 방법들이 있다.

예를 들면 printf는 어떻게 만들어져 있을까라든지 file I/O는 어떻게 하는 것인지...
무턱대고 쓸 줄만 알았지 사실 어떻게 구현되어 있는지는 잘 모르는게 사실이다.

문득 틈틈히 이 책부터 공부해야지... 하는 생각이 들었다.
몇 가지 기초적인 언어들을 기반으로 이렇게 복잡하고 다양한 프로그램들을 짜내는 것...
그게 바로 프로그래밍 언어의 묘미(?)가 아닐까 한다.

당분간 CS와 굿바이해야 해서 그런지
은근 잼있는 것 같다. ㅋㅋ

'[일상의 한마디]' 카테고리의 다른 글

교수님과의 졸업논문 최종 미팅...  (0) 2007.06.20
이메일의 신뢰성(reliability)  (0) 2007.06.20
내신 실질 반영률 문제...  (3) 2007.06.18
대학교 공식 종강  (0) 2007.06.15

댓글을 달아 주세요