Open ID와 Recaptcha가 당분간 지원되지 않습니다. 새 버전의 PHP에서 해당 확장기능이 제대로 작동하지 않습니다. 최대한 빨리 복구해보겠습니다.

세그멘테이션 폴트

문제

C#으로 문자열에서 문자를 삭제하는 효율적인 함수를 작성하라. 함수 원형은 다음과 같다.

string removeChars(string str, string remove);

remove라는 인자로 전달된 문자열에 있는 모든 문자를 문자열에서 삭제한다.

시도 1

배열에서 원소를 삭제하는 방식이 있다. 이 방식은 문자를 삭제할 때마다 데이터를 이동시켜야 하며 최악의 경우에 O(n^2)이다.

시도 2

문자열의 맨 뒤부터 시작해서 앞으로 오면서 삭제를 하면 어느 정도 효율이 좋아지나, 여전히 O(n^2)이다.

시도 3

임시 문자열 버퍼를 할당하고 고친 문자열을 그곳에 저장하는 방법도 있다. 삭제할 문자는 건너뛰고 남겨야 할 문자들만 임시 문자열에 저장하면 된다. O(n)으로 효율이 좋아지지만 원본 문자열 크기만큼 임시 버퍼를 만들어야 하므로 메모리 오버헤드가 있다. 또한 바뀐 문자열을 다시 원래 문자열로 복사하는 시간도 있다.

정답

세 번째 시도를 조금만 손보면 된다. 문자열의 위치를 따라가는 변수(하나는 출발지, 하나는 목적지)를 두 개 둔다. 위치는 둘 다 0에서 시작한다. 출발지는 한 글자 읽을 때마다 하나씩 증가하며, 목적지는 한 글자 쓸 때마다 하나씩 증가한다. 즉, 한 문자를 복사할 때는 두 위치를 모두 증가시키지만, 문자를 지울 때는 출발지만 증가시킨다. 원본 문자열에서 한 글자를 읽고 나면 그 문자는 더 필요 없다. 나중에 변경된 문자열을 그 위에 덮어쓰기 때문이다. 이런 방식은 O(n)에 불과하다.

이제 remove의 크기가 m이라고 하자.

remove가 m이면 네 번째 방식은 O(nm)이 된다. 그러나 remove를 해시로 바꾸면 O(n+m) = O(n)에 처리 가능하다. m의 값이 클 땐 해시로 처리하는 방식이 유리하다.