태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
문제) 주어진 문자열 배열에서 세번째로 긴 문자열 출력하라.

지난 번 폰 인터뷰에 나왔던 문제이고, 이전 포스팅인 '배열에서 두번째로 작은 수를 구하기'와 거의 유사하다. 다만, string class를 좀 제대로(?) 사용해보고자 다시 해봤다.

소스 보기

문제) 문자열 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++도 아닌 오묘한 코드이다.

소스 열기

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

소스보기

이번에는 string에서 반복되지 않는 첫번째 문자를 찾아본다. 예를 들면 "appropriate"에서 o를 선택하면 되는 것이다. 문자열의 길이를 n이라고 하면 O(n)인데 실제로는 n을 최대 두번 읽는다. 더 좋은 방법은 없을까?
#include <iostream>

using namespace std;

char firstchar(string str) {
	char ch[128];
	char tmp;
	
	for (int i = 0; i < 128; i++)
		ch[i] = 0;
	
	int len = str.length();
	
	for (int i = 0; i < len; i++) {
		tmp = str.at(i);
		ch[tmp]++;
	}
	
	for (int i = 0; i < len; i++) {
		tmp = str.at(i);
		if (ch[tmp] == 1)
			return tmp;
	}
	return NULL;
}

main() {
	string str[] = {"Niceee", "babbyddas",
		"Gorooeadsjfabdfmadslfdlfa", "a", "aabb"};
	
	for (int i = 0; i < 5; i++)
		cout << firstchar(str[i]) << endl;
}
  1. Favicon of http://zzun.net BlogIcon zzun 2010.02.19 16:25 신고

    반복되지 않는 문자를 간단히 solo 라고 하면,

    루프를 한 번만 돌면서...
    1. 지금현재까지의 first solo
    2. 해당 solo가 탈락(중복)되었을 때의 next solo(배열)

    위 두 가지 정보를 유지/갱신하면서 돌면 될 것 같은데
    얼추 생각해봐도 코드가 매우 복잡할듯;

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.02.19 17:24 신고

      abacac의 경우 순서대로 a ab b bc bc a가 되어 a가 답이 되어야 하는데, 결국 이 solo 리스트에 현재 index의 문자가 있는지 매번 확인을 해야하니까 worst case가 O(n)이 되고, 전체는 O(n^2)이 되지 않나? 결국 걍 2n하는게 O(n)라서 더 나을 듯 한데. BST나 heap으로는 안될 것 같고.

      잘 모르겠다.

  2. broYobi 2010.02.22 18:03 신고

    이론적인 것만 고려한다면

    피보나치 힙을 (넣을 때, O(1), 뺄 때 O(log(n)) 사용하면 가능할 것 같네..

    하지만 실제로는 별 이익이 없네용....

  3. 2016.04.07 04:21

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.07 12:06 신고

      aba가 입력이면 b가 출력돼야 하는데 올려주신 코드에서는 nonchar가 나오게 됩니다. :)

      제 코드에서... 만약 주어진 문자열(str)이 엄청나게 길고 문자의 종류(위에서는 128개로 가정)가 적다면, 문자열은 한 번 읽고 특정 문자열의 등장 여부를 담은 배열(ch) 값을 한 번 search하는 것으로 바꾸는 식으로 위 코드를 개선할 수 있습니다.

      6년 전에 쓴 글인데 공부에 도움이 되었다니 기쁘네요. 덕분에 저도 다시 한 번 살펴봤습니다.

    • 2016.04.07 13:10

      비밀댓글입니다

  4. 2016.04.07 23:54

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.08 11:30 신고

      음.. aba에 대해서는 올바른 답인 b를 출력하는데, abbe를 넣으면 a가 아닌 e라는 오답을 출력하네요.

  5. 2016.04.08 23:11

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.09 04:20 신고

      이번에는 abcdedcba를 넣으면 e가 나와야 하는데, nonchar가 나옵니다.

      이 문제를 if문으로 처리하는 접근은 좋지 않습니다. 몇 가지 입력에는 유효한 답을 내겠지만, 입력 문자열이 길어지면 반례가 반드시 존재할 수밖에 없습니다. 왜냐하면, 답이 될 수 있는 후보를 다 기억하고 있어야 하는데, 이를 기억하려면 메모리 공간이 최악의 경우 O(n)이 필요하다는 이야기이고, 한두 변수만 추가해서는 해결할 수 없습니다.

      제가 본문에 제시하고 댓글에서 개선한 counting 접근이 유효한 솔루션이라고 생각합니다. (다른 더 나은 방법이 있을지는 모르겠지만...)

  6. 2016.04.09 04:37

    비밀댓글입니다

  7. 코리온 2016.10.11 15:40 신고

    비밀댓글 좀 그러네요 ^^

    좋은 내용 잘 보고갑니다.

+ Recent posts