[Algorithm] c++ 문자열 split

C++ 로 코딩테스트를 준비하다보면 문자열을 쪼개야 하는 상황이 발생한다. 이 때 문자열을 단 하나의 문자로 쪼개는 경우가 있고 때로는 문자열을 기준으로 쪼개는 경우가 있다. 이 포스팅을 통해 그 일련의 과정을 찬찬히 살펴보자.

문자열을 쪼갤 때면 파이썬으로 갈아탈까 하는 생각이 들곤 한다.. 잘 알아두자..

Example

이 포스팅에서 최종적으로 해결하고자 하는 문제는 다항식 쪼개기이다. 즉 다음과 같은 식을 쪼개는 것을 목표로 하여 코드를 작성해보자.

\[4x^3 + 5x^2 + 7x\]

위 식을 4x^3 + 5x^2 + 7x^1 로 표현하자. 우리는 이 식을 4x^3 , 5x^2 , 7x^1 로 나눌 것이다.

stream 과 buffer

c++ 로 코딩을 하며 자주 사용하는 함수가 있다. 바로 cin 과 cout 이라는 함수이다. 이 함수를 사용하려면 iostream 이라는 헤더를 임포트 해야한다.

이 iostream 은 input output stream 의 줄인말이다. 한 번 우리가 사용하는 cin 과 cout 의 기능을 떠올리며 stream 의 의미를 직관적으로 생각해보자.

키보드에서 입력한 무언가를 프로그램해서 사용할 수 있게 가져오는 것이 cin 이다. 프로그램에서 작성한 무언가를 콘솔창에서 볼 수 있게 보내주는 것이 cout 이다. 즉 키보드의 데이터가 프로그램으로, 프로그램의 데이터가 콘솔창으로 이동할 수 있게 도와주는 헤더가 바로 iostream 인 것이다.

이와 같이 데이터의 흐름을 이해할 떄 반드시 알아야 하는 것이 stream 이라는 개념이다. stream 이란 바이트들의 흐름이다. 키보드에서 입력한 데이터가 내가 만든 c++ 프로그램으로 도달하기 까지의 흐름과 c++ 프로그램에서 출력한 데이터가 내 콘솔창에 도달하기 까지의 흐름이다.

아래 그림과 같이 stream 을 강(river) 이라고 생각해보자. 저 길게 늘어진 물줄기가 내가 작성한 프로그램으로 들어오는 데이터들이다.

한편, 프로그램은 정보를 한 번에 1 바이트밖에 처리하지 못한다. 만약에 디스크에 저장되어 있는 파일로부터 한 번에 한 문자씩만 읽어들인다고 생각해보자. 하나의 글자를 읽을 때마다 매번 디스크에 접근한다고 생각하면 굉장히 비효율적인 방법이다. 이 때 필요한 개념이 buffer 이다. buffer 는 메모리 레벨의 개념으로 디스크에서 데이터를 한번에 받아온 이후 프로그램으로 1 바이트씩 보내주는 역할을 수행한다. 즉 위 그림에서 댐 을 버퍼라고 생각하면 된다.

프로그램은 데이터를 디스크 레벨에서 읽어들이는 것보다 메모리 레벨에서 읽어들이는 것을 훨씬 좋아한다. 훨씬 빠르고 효율적이다. 때문에 하나의 글자를 읽을 때마다 매번 디스크에 접근하는 것보다 디스크의 데이터들을 메모리 (buffer) 에 쌓아놓고 필요한 글자를 하나씩 buffer 에서 읽어오면 된다. 즉 댐에 디스크의 데이터들을 보관해 두었다가 프로그램에 조금씩 흘려보내준다고 생각하자.

iostream 의 getline()

자 다시 본론으로 돌아오자. 그래서 어떻게 문자열을 쪼갤 수 있을까? 보통 문자열을 특정 문자에 대해 쪼개기 위해 사용하는 함수로 getline() 이 있다. getline을 사용하기 위해서는 iostream 헤더를 임포트 하면된다. getline 의 파라미터는 istream& getline (char* s, streamsize n, char delim ); 이다.

사용할 때는 스트림.getline(저장할곳, 받아올문자개수, 구분자) 의 형태로 작성하면 된다. 구분자의 기본 설정값은 \n , 줄바꿈 문자이다.

더 자세한 사항은 문서를 찾아보면 되고, 사실 이 단락에서 가장 강조하고 싶은 내용은 char* 타입과 string 타입을 구분해야 한다는 것이다.

예시를 보자.

char str[100] 의 변수에 getline() 을 통해 입력받은 값을 저장하려 한다. 이 때, 받아올 문자의 개수는 10개로 설정하였다. 입력값으로 Hi World! 를 받은 후에 str 을 출력하여 저장된 값을 확인해보자.

출력 결과 Hi World! 가 잘 저장되어 있음을 확인할 수 있다.

그렇다면 이번에는 Hello World! 를 입력값으로 받아보자.

출력 결과 str 에 Hello Wor 까지만 저장되어 있음을 확인할 수 있다. 이렇게 손실된 데이터가 저장된 이유는 우리가 cin.getline(str, 10) 와 같이 10개의 문자만 받아오도록 코드를 작성했기 때문이다. (마지막 문자는 null 값으로 저장되기 때문에 실제로는 9개의 문자만 저장된다)

여기서 iostream 헤더의 getline 의 한계점이 파악된다. 바로 입력데이터의 최대 개수를 알고있어야 한다는 점이다. 이 점을 극복하기 위해서 sstream 의 getline 함수를 사용한다.

다음 그림에서 알 수 있듯이 stringstream 은 iostream 이 등장한 이후에 등장한다. 왜냐하면 string 헤더가 iostream 헤더 이후에 생성되었기 때문이다. 순서 상 당연하게도 iostream 만을 이용해서 string 타입의 데이터를 온전히 다루지 못한다. string 데이터의 흐름을 온전하게 담당하는 stream 을 새롭게 만들었고 이게 바로 stringstream 인 sstream 이다.

string 이전에 문자열을 다루는 데이터 타입이 char* 이다. 때문에 char* 를 이용하는 함수에 string 을 넣으면 다음과 같이 오류가 발생한다.

즉 char* 와 string 은 분명하게 다른 것이다.

sstream 의 getline

아까 iostream 의 getline 사용법은 스트림.getline(저장할곳, 받아올문자개수, 구분자) 라고 했었다. 또한 getline 을 사용할 때 받아올 문자 개수를 명확히 선언해야 한다는 것이 한계점으로 다가오는 것을 보았다. 그렇다면 이를 대안하기 위해 사용하는 sstream 의 getline 은 어떻게 사용할까?

바로 getline(스트림, 저장할곳, 구분자) 의 형태로 사용한다. (더 다양한 사용법과 자세한 사항은 공식 문서를 참고하자)

아까 실패했던 Hello World! 를 입력으로 받은 후 출력하는 경우를 다시 시도해보자.

아까와는 달리 온전히 문자열이 출력 되는 것을 알 수 있다. 구분자를 '\n' 이 아닌 ' ' 로 설정하면 어떤 결과가 나올까?

공백 ' ' 을 기준으로 쪼개어져 Hello 만이 str 에 저장된 것을 확인할 수 있다.

이 때 기억해야 할 내용은

1. 남은 데이터 (예시에서 ‘World!’) 는 여전히 stream 에 남아있다.

2. 구분자 (예시에서 공백 ' ') 는 stream 에서 버려진다.

는 것이다.

자 거의 다 왔으니 이제 문자열을 한 번 쪼개보자 !

문자열 split (1)

우선 코드부터 보여주면 다음과 같다.

아까와는 달리 키보드로부터 데이터를 입력받지 않는다. cin 이라는 stream 은 표준입력장치(키보드) 와 프로그램 사이에서 존재한다. 이번 경우에는 키보드로부터 입력을 받지 않기 때문에 stringstream 중 input 을 담당하는 istringstream 을 이용한다.

위 코드는 Hi my name is Gildong 을 ' ' 인 공백문자로 쪼갠다. 정확히는 Hi my name is Gildong 이 입력된 stream 에서 공백문자까지 읽어온 후 공백문자를 버린 다음 읽은 문자열을 temp 에 저장한다. 그 후 res 라는 vector 에 temp 에 들어있는 값을 저장한다. 매 while 문 마다 stream 으로부터 공백문자 전까지 데이터를 읽어와 저장하므로 쪼개진 모든 문자열을 저장할 수 있다.

while 문은 stream 에 데이터가 끝난 경우, 기대하는 데이터를 읽지 못한 경우, 알 수 없는 이유로 stream 이 손상된 경우 break 된다. 더 자세한 사항은 stream state 에 관한 내용 중 eofbit, badbit, failbit 등을 살펴보자.

위 코드가 c++ 에서 문자열을 단 하나의 문자 기준으로 쪼개는 방법이다. 하지만 여전히 한계점이 존재한다. 위 코드로는 문자열을 또 다른 문자열로 쪼개지는 못한다. 우리는 4x^3 + 5x^2 + 7x^1 을 쪼개려 한다. 이 때 구분자는 " + " 로 길이가 3인 문자열이다.

다음 단락에서 이 문제를 해결해보자.

문자열 split (2)

우리는 두개의 함수를 이용하여 문자열을 또 다른 문자열로 쪼갤 것이다.

바로 string 헤더의 함수인 find 와 substr 함수이다.

find 의 대략적인 사용방법은 다음과 같다. 문자열.find(탐색대상, 탐색시작위치) - 특정 문자열의 탐색 시작 위치에서부터 탐색을 시작한다. 탐색 대상이 발견된 경우 탐색 대상의 맨 앞이 문자열에서 차지하는 인덱스를 반환해준다.

그 다음으로 substr 의 사용법을 알아보자. substr 의 대략적인 사용방법은 다음과 같다. 문자열.substr(시작위치, 개수) - 특정 문자열의 특정 위치로부터 특정 개수만큼의 길이를 가진 부분문자열을 반환하는 함수이다.

드디어 우리는 다항식을 쪼개는데 필요한 지식을 다 배웠다. 다항식은 다음과 같이 쪼개면 된다.

드디어.. 성공했다..

한편, find 함수는 특정 인덱스를 찾지 못했을 때 npos 를 return 한다. npos 는 string class 의 최대 허용 문자 수를 의미하며 이 값은 unsigned int 형의 -1 값고 동일하다. 이를 인지하고 위 코드를 보면 더욱 잘 이해가 될 것이다.

Reference

1. 댐 사진 출처 - https://builtenvironment.tumblr.com/page/18
2. 전반적인 내용 - C++ 기초 플러스 6판