[실전 알고리즘] 부록 A - 문자열 기초

 

안녕하세요, 첫 번째 부록을 시작해봅시다. 부록도 0x01 0x02 0x03 이렇게 붙여야하나 고민을 좀 했는데 다른 책들을 보니 부록은 A, B, C로 붙이는게 국룰인 것 같아 부록 A로 이름 붙였습니다. 강의를 만들다보니 뭔가 추가적인 설명이 필요하겠다 하는 개념들이 있었는데 그렇다고 한 단원으로 만들기는 좀 애매한 내용들이 있어서 부록으로 소개해드리게 되었습니다. 예를 들어서 이번 부록에서 소개할 내용을 보면 제 강의 구성 상에서 KMP나 트라이와 같은 문자열 알고리즘이 제일 뒤에 나와서 문자열에 대한 기초적인 내용을 강의 극후반까지 소개를 못드렸고 이렇게 뒤늦게나마 메소드들을 소개하는 강의를 부록으로 만들게 되었습니다. 그래서 제 강의는 AS까지 확실히 해드린다는거 한 번 인지해주시고, 나중에 따로 어딘가에 적어두겠지만 부록 A, B, C는 0x11강 그리디까지 본 다음 익히고 부록 D, E는 0x1F강 트라이까지 본 후에 익히는 것을 의도하고 있습니다.

 

이번 단원에서는 새로운 알고리즘이나 개념을 다루지는 않을거고 C++에서 문자열을 다루는 방법과 여러 메소드들을 알아보고자 합니다.

 

강의에 앞서 먼저 알려드리고 싶은게 있는데, 저는 알고리즘 문제를 풀 때 C++를 굉장히 선호하는 편임에도 불구하고 문자열 처리가 복잡할 때 만큼은 파이썬을 씁니다. 단순히 문자열을 이어붙이고, 단어를 찾는 정도야 C++로 못할건 없지만 그 정도가 아니라 예를 들어 HTML 파싱 처럼 일단 보면 딱 머리가 아픈 그런 문제를 보면 그냥 바로 파이썬을 꺼내듭니다. 그래서 인생은 짧기 때문에 파이썬이 필요하다는 교훈처럼 문자열 처리가 복잡하면 C++ 말고 파이썬을 쓰는걸 추천드립니다. 또 사실 명색이 개발자면 파이썬 정도는 익혀두면 두고두고 쓸 곳이 많기도 합니다. 하지만 현실적으로 파이썬으로 알고리즘 문제를 푼 경험이 많지 않으신 분이라면 문자열 처리 단 하나만 보고 파이썬을 새로 익히는건 다소 비효율적이긴 합니다. 그래서 파이썬도 보조 무기로 익혀둘지 그냥 C++로만 할지는 각자가 선택을 하면 되지만, 이런저런 이유로 꼭 C++로 문제를 풀어야만 하는 상황이라면 문자열을 char*으로 관리하는 대신 C++의 string을 사용하시는게 훨씬 낫습니다. char*는 지원하는 메소드도 불편하고 문자열 끝에 반드시 NULL이 있어야한다는 점 때문에 조금만 삐끗해도 버그를 발생시킬 수 있습니다. 혹시 학부때 프로그래밍 기초 강의에서 C언어로 과제를 해본적이 있다면 무슨 의미인지 쉽게 이해할 수 있을 것입니다. 비유를 해보자면 char*은 뗀석기, C++의 string은 간석기, 파이썬은 철기 이런 느낌이라 문자열 사용이 복잡할 경우에는 파이썬 사용을 추천하지만 꼭 C++로 구현을 하겠다면 char* 대신 string을 사용하는 것을 강력하게 추천합니다.

 

사실 문제를 풀거나 개발을 하다보면 자연스럽게 문자열에 대한 처리가 필요한 일이 종종 있을 수 있어서 여기 나와있는 메소드 중에서 한 번쯤은 접해본게 있을 수도 있습니다. 각 메소드들을 보면 제가 여기 단순히 예시로 써놓은 방법 이외에도 인자를 추가로 넘겨서 유용하게 써먹을 수 있는 경우가 있긴 하지만 그런 것들을 하나하나 소개하기에는 너무 많아서 자세한건 문서를 참고해보시고 substr, replace, find, erase, insert 등이 있구나 하는 정도로만 이해하고 가겠습니다. 또한 find에서 존재하지 않을 경우에는 18번째 줄과 같이 string::npos를 반환하는데 string::npos는 사실 -1과 같기 때문에 find 결과가 없음을 확인하고 싶으면 -1과 비교를 해도 상관없습니다. (코드)

 

C++ string에는 이렇게 메소드들이 적당히 있어서 적재적소에 써먹을 수 있지만 예를 들어 공백이나 콤마를 기준으로 단어를 나눌 때와 같이 구분자를 기준으로 문자열을 나눠주는 함수가 없습니다. 문자열 처리를 연습할겸 문자열 s를 받아 구분자 sep을 기준으로 문자열을 나눈 결과를 반환하는 split 함수를 작성해봅시다. sep은 꼭 1글자일 필요가 없다는 점에 유의하세요. 위의 string_example.cpp에서 제가 작성한 split 함수를 날리고 직접 만들어보세요.

 

저는 find 함수의 2번째 인자로 처음 탐색을 시작할 위치를 보낼 수 있다는 사실을 이용해 s 안에 sep이 있는 위치들을 찾아 적절하게 단어를 잘라 vector ret에 저장했습니다. 여기서 구현의 편의를 위해 pos를 두는 대신 s라는 문자열 자체를 s = s.substr(nxt_pos + sep.size());와 같이 바꾸면서 처리를 할 수 있지만 이렇게 될 경우 본문에 써놓은 것과 같이 A A A ... A와 같은 문자열에서 공백을 기준으로 분리할 때 O(|S|)가 아니고 O(|S|²)에 동작한다는 단점이 있습니다. 왜 O(|S|²)이냐면 공백으로 저 문자열을 분리할 경우 단어가 대략 |S|/2개 생기기 때문에 s에 s.substr(nxt_pos + sep.size());를 대입하는 연산이 대략 |S|/2번 발생하고, 또 각 연산에 필요한 시간복잡도가 평균적으로 O(|S|)여서 그렇습니다. 그렇기 때문에 지금의 코드와 같이 pos라는 인덱스 정보만 별도로 가지고 다니면서 필요에 따라 substr로 문자열을 자르는 방식으로 구현하는걸 추천드립니다.

 

비단 split 함수가 아니더라도 문자열에서 무언가 연산을 할 때 시간복잡도를 고려하지 않는 경우를 종종 볼 수 있는데, 문자열의 길이가 이를테면 1000 이하 정도로 작아서 크게 시간복잡도가 상관이 없는 상황이라면 큰 문제가 없습니다. 하지만 길이가 10만 이상으로 커서 시간복잡도가 길이에 대한 제곱 이상일 때 시간 초과가 나는 경우라면 반드시 시간복잡도를 꼼꼼하게 따질 필요가 있습니다. 이 주의사항은 제가 이 부록을 통해 꼭 전달을 해드리고 싶었던 내용이고 또 문자열과 관련해 흔하게 볼 수 있는 실수 중 하나입니다. 지금 이 코드의 시간복잡도는 얼마일까요? N은 반복 횟수인 1000000이라고 생각해서 시간복잡도가 N에 대해 어떻게 될지를 생각해보면 되겠습니다.

 

얼핏 보기에는 O(N)일 것 같지만 이 코드는 O(N²)에 동작합니다. 써놓은 것 처럼 매 덧셈마다 새 객체를 만들고 그걸 s에 대입하기 때문에 그렇습니다. 당연히 a로 이루어진 길이 N의 문자열을 O(N²)에 만들고 싶은 사람은 없을 것이기에 이걸 O(N)에 수행하도록 변경한 코드는 아래에서 확인 가능합니다.

 

+= 연산자를 이용하면 시간복잡도가 더해지는 길이에만 영향을 받아 총 O(N)에 수행 가능합니다. 이 차이로 인해 뜬금없는 시간 초과를 받지 않도록 주의합시다. 이외에도 시간복잡도를 줄여야 할경우 split 함수에서 본 것과 같이 문자열 자체에서 삭제나 추가 등을 하는 대신 인덱스 정보만을 가지고 영리하게 처리할 수 있는 방법은 없을지 고민해보도록 합시다.

 

이제 바로 문제를 풀어봅시다. BOJ 1543번: 문서 검색을 보시면 find 함수를 쓰면 되겠다는 느낌이 오고 또 find 함수에서는 pos 인자를 넘겨서 내가 찾고 싶은 단어가 위치 pos 이후로 언제 등장하는지를 알 수 있습니다. 이 때 이후라고 함은 위치 pos를 포함합니다. 저기 써놓은 T.find(P, pos)의 설명을 읽어보세요. "abcabc".find("abc", 1)로 예를 들면 "abcabc"에서 "abc"가 등장하는 위치를 찾는데, 인덱스 1 이후의 위치를 찾기 때문에 3을 반환합니다. 그 밑의 예시는 직접 생각해보면 어렵지 않게 이해할 수 있을 것이라고 생각합니다. 이 pos 인자를 적절하게 정해서 중복되어 세는 것은 빼야한다는 조건을 처리할 방법을 고민해봅시다.

 

방법은 비교적 간단합니다. find를 통해 단어를 찾은 이후에는 그 위치에서 P.size()만큼 더한 값을 pos의 인자로 넘기는 작업을 반복하면 됩니다. 이렇게 하는 대신 단순히 1만 더할 경우에는 예제 입력 4와 같이 "aaaaaaa"에서 "aa"의 등장 횟수를 셀 때 중복되는 경우가 생길 수 있습니다. 적힌 내용이 조금 헷갈리면 바로 코드를 보면서 이해해보도록 합시다.

 

문제의 조건에서 문서와 단어에 공백이 있을 수 있다고 했으니 getline으로 입력을 받고 11-15번째 줄과 같이 이전에 단어가 등장한 위치를 f에 저장했다가 다음 탐색을 할 때에는 find의 pos 인자로 f + p.size()를 넘겨 중복되어 세지 않도록 했습니다. 인자로 넘기는게 f + p.size()인지, 아니면 f + p.size() + 1이나 f + p.size() - 1인지 등이 은근 헷갈릴 수 있고 이렇게 인덱스에서 1 차이로 혼돈이 오는건 비단 이 문제 뿐만 아니라 다른 문자열 문제에서도 비일비재한 일입니다. 그럴땐 차분하게 손으로 직접 작은 예시를 써보며 인덱스를 정확하게 맞추면 됩니다. (코드)

 

다음 문제는 BOJ 2941번: 크로아티아 알파벳입니다. C++ string의 어떤 메소드를 활용하면 좋을까요?

 

저는 replace를 이용해 크로아티아 알파벳을 계속 다른 문자로 치환하는 방법을 사용했습니다. 만약 크로아티아 알파벳을 그냥 지워버리면 어떤 문제가 있을까요?

 

그렇게 하면 nnjj와 같은 예시에서 오답을 낼 수 있습니다. 구현을 직접 해봅시다.

 

구현에서 크게 특이사항은 없습니다.

 

이번 단원에서는 주로 C++ string의 사용법에 대해 알아보았습니다. 문자열 처리가 복잡한 문제들은 구현이 약간 까다롭게 느껴질 수 있지만 대부분 특별한 알고리즘이 필요한 문제들은 아니기 때문에 메소드들을 잘 익히고 인덱스 실수가 발생하지 않도록 주의하면서 문자열 관련 구현을 많이 연습해보다보면 그렇게 어렵지 않게 잘 풀어낼 수 있습니다.