'C' 태그의 글 목록

[C] 회전된 문자열인지 판별

[아는게 힘이다]/[프로그래밍] 2010. 3. 10. 15:56

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

#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;
}

저작자표시비영리변경금지

'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글

[C++] 부분 문자열 검사 (Substring) (0)	2010.03.19
[C++] 전화 번호 문자열 변환 (Telephone Words) (0)	2010.03.19
[C] 회전된 문자열인지 판별 (0)	2010.03.10
[C] 문자열에서 반복되는 가장 긴 부분 문자열 (8)	2010.03.06
생각하는(?) 실용주의(?) 프로그래머 (2)	2010.03.04

Tag C, 문자열, 순환, 알고리즘

트랙백 0개, 댓글 0개가 달렸습니다

댓글을 달아 주세요

[C] 문자열에서 반복되는 가장 긴 부분 문자열

[아는게 힘이다]/[프로그래밍] 2010. 3. 6. 14:05

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에서 보고 감탄했는데, 알고랭이 좀 했다하는 애들은 중학생들도 아는 알고리즘이라는 것을 알고 나니 부끄럽다. -_-;

#include <stdio.h>
#include <string.h>
#include <stdlib.h>	// for malloc

int compare(const void *a, const void *b)
{
	return strcmp(*(char**)a, *(char**)b);
}

int complen(const void *a, const void *b) 
{
	int len, max = strlen((char*)a);
	if (strlen((char*)b) < max) max = strlen((char*)b);
	for (len = 0;len < max; len++) {
		if (((char*)a)[len] != ((char*)b)[len])
			return len;
	}
}

int main() 
{
	char buf[] = "abcdaabcdefabcf";
	int len = strlen(buf);
	int maxlen = 0;
	int idx = 0; 
	int tmp = 0;
	int i = 0;

	char *sa[len];	

	for (i = 0; i < len; i++)
		sa[i] = &buf[i];
	qsort(sa, len, sizeof(char*), compare);

	for (i = 0; i < len - 1; i++) {
		tmp = complen(sa[i], sa[i+1]);
		if (tmp > maxlen) {
			maxlen = tmp;
			idx = i;
		}
	}

	char *longstr = (char*)malloc(sizeof(char)*maxlen+1);
	strncpy(longstr, sa[idx], maxlen);
	printf("idx: %d maxlen: %d str: %s\n", idx, maxlen, longstr);

	free(longstr);

	return 0;
}

저작자표시비영리변경금지

'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글

[C++] 전화 번호 문자열 변환 (Telephone Words) (0)	2010.03.19
[C] 회전된 문자열인지 판별 (0)	2010.03.10
[C] 문자열에서 반복되는 가장 긴 부분 문자열 (8)	2010.03.06
생각하는(?) 실용주의(?) 프로그래머 (2)	2010.03.04
[CS] 연결 리스트 뒤집기 (Reverse Linked List) (6)	2010.02.28

Tag C, suffix array, 알고리즘, 최장공통문자열

트랙백 0개, 댓글 8개가 달렸습니다

댓글을 달아 주세요

broYobi 2010.03.06 21:56 댓글주소 수정/삭제 댓글쓰기
clever 하네
- 조나단봉 2010.03.06 22:32 신고 댓글주소 수정/삭제
  그러게
아로운 2014.08.28 12:18 댓글주소 수정/삭제 댓글쓰기
블로그를 참고하면서 공부하고 있는 1인입니다.
좋은 컨텐츠를 제공해 주셔서 감사를 드립니다, 많은 도움이 되고 있어요.
(char*)대신 *(char**)을 쓰는 이유를 알 수 있을까요?
실제로 코딩해봤는데 strcmp에서 정렬이 안되더군요.
- 조나단봉 2015.11.18 04:18 신고 댓글주소 수정/삭제
  답변이 너무 늦었지만, 훗날을 위해 답변 달아봅니다.
  
  buf 배열은 대상 문자열(e.g., banana)을 담고 있고, sa 배열은 대상 문자열의 각 문자를 가리키는 포인터를 담고 있습니다. 예를 들면, sa[2]는 첫번째 "n"의 주소를 갖고 있습니다. 따라서 buf는 char* 타입이고, sa는 char** 타입입니다.
  
  *(char**)을 살펴보면 일단 (char**)는 const void* 타입을 캐스팅한 것인데, a가 sa의 원소(element)를 가리키는 포인터가 되어야 하므로, sa의 타입인 char**로 캐스팅합니다.
  
  앞에 있는 *는 역참조(dereferencing)를 하기 위한 것인데, 우리가 비교하려는 대상은 sa 배열의 값 자체가 아니라 그것이 참조하고 있는 문자열 자체이므로 *를 사용해서 비교되는 대상이 buf 배열에 있는 문자열의 일부가 되도록 하기 위해서입니다.
  
  비교 대상은 sa의 각 원소가 가리키고 있는 문자열인데, 정렬되어야 하는 값은 sa의 각 원소입니다.
hexists 2014.12.03 17:16 신고 댓글주소 수정/삭제 댓글쓰기
정리해주신 글 보고 잘 이해했습니다. 감사합니다.
와 2015.10.16 12:20 댓글주소 수정/삭제 댓글쓰기
문자열 끊는 법을 몰랐는데, 이 글로 알게되었네요 감사합니다.
공부 2017.08.21 00:56 댓글주소 수정/삭제 댓글쓰기
공부중인 학생인데요, O(n*nlogn)이 아니라, O(nlogn+n) 아닌가여?
따로 도니까...
- 조나단봉 2017.08.21 03:37 신고 댓글주소 수정/삭제
  본문에서 '문자열 비교에서 n'이라고 한 것은 sorting 내에서 2개의 문자열 간 비교를 말한 것입니다. sorting 후 인접 문자열 간의 비교가 아닙니다. 본문 문장에 오해의 소지가 조금 있었을 수도 있겠는데, 원래 의도는 이렇습니다.
  
  보통 sorting의 예에서는 element 개수가 dominant하고 각 element간의 비교는 O(1)입니다. (e.g., 문자열의 길이가 상수) 그런데 이 문제에서는 element 개수가 문자열의 길이와 같기 때문에 아래와 같이 계산해야 합니다.
  
  element 개수를 n이라 할 때 우리가 사용한 sorting에서 비교 횟수는 O(nlogn)라고 합시다.
  
  이 문제에서는 두 element를 비교하는 compare 함수도 O(n)가 됩니다.
  
  따라서 이 sorting에서 문자(char) 비교 횟수는 총 O(n*nlogn)이 됩니다.
  
  감사합니다.

ANSI C 공부...

[일상의 한마디] 2007. 6. 19. 13:40

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

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

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

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

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

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

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

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

Tag ANSI C, C, 프로그래밍

트랙백 0개, 댓글 0개가 달렸습니다

'C'에 해당되는 글 3건

[C] 회전된 문자열인지 판별

'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글

댓글을 달아 주세요

[C] 문자열에서 반복되는 가장 긴 부분 문자열

'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글

댓글을 달아 주세요

ANSI C 공부...

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

댓글을 달아 주세요

공지사항

카테고리

태그목록

글 보관함

달력

링크

조나단봉

LATEST FROM OUR BLOG

LATEST COMMENTS

BLOG VISITORS

« 2021/01 »
일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31