[CodingInterview] 01 배열과 문자열(STL std::String)

이번에 살펴볼 주제는 코딩인터뷰 배열과 문자열파트에 C++ String에 대해 정리해보도록하겠습니다.

책은 자바위주로 되어있지만, 제가 알고리즘 테스트에 사용하는 언어는 C++14이기 때문에 Java의 StringBuilder 대신에 C++ String STL에 대해 다루도록 하겠습니다.

 

# 일단 문자열이 무엇일까요?

 

예를 들어보겠습니다. "Algorithm" 라는 문자열이 있다고 가정하겠습니다.

 

A

l

g

o

r

i

t

h

m

NULL('\0')

 

당연히 생각하신데로 나오셨나요? 네, 그렇습니다. C언어나 C++을 사용해보신분들은 알고 계실것이라 생각이 듭니다. 하지만, 모르시는분들이 있으시기 때문에 짚고 넘어가겠습니다.

 

현재 우리는 "Algorithm"이라는 문자열을 가지고 있습니다. 위의 구조에서 보면 의문이 드실겁니다.

 

# 왜 갑자기 뜬금없이 NULL이라는 문자가 왜 나오는거지?

 

분명히 우리는 "Algorithm"이라는 문자열을 가지고 있는데 NULL('\0')이라는 문자가 등장하게 됩니다.

모든 문자열에는 문자열의 끝을 확인 할 수 있어야합니다. 

말 그대로 한국어에서 "마침표"가 있는것과 같다고 생각하시면 됩니다.

문자열의 영역에서 NULL('\0')을 만나게 되면 C++컴파일러는 "여기가 문자열의 끝" 이라고 인식을 합니다.

 

보통 모든 문자열을 순환할 때 이런식으로 쓰시는것을 보셨는지는 모르겠지만, 응용하자면

 

    char arr[30] = "Algorithm";    
    char *arr2[10] = { NULL, };    
    int index = 0;                     

    char *ptr = strtok(arr, " ");   

    while (ptr != NULL)            
    {
        arr2[index] = ptr;             
        index++;                       
        ptr = strtok(NULL, " ");   
    }

 

다음과 같이 사용 할 수 있습니다. 위의 예제는 String 문자열을 Tokenizer를 통한 분리를 하는 코드입니다.

 

간략히 코드를 설명하자면, arr이라는 문자열에 있는 "Algorithm"을 " " 공백기준으로 StringTokenizer를 통하여 포인터 *ptr를 가리키게 합니다. arr에 있는 String값을 !=NULL을 만나기전까지 계속 진행하게 되면서 문자열의 Tokenizer을 종료하게 됩니다. 이와 같이 문자열을 NULL('\0')값으로 제어 할 수 있습니다.

 

 

이제 C++에서 문자열을 확인해보겠습니다. 문자열은 배열형태로 메모리상에 공간을 차지하게됩니다.

문자는 char형은 영문 1byte / 한글, 일본어, 중국어 2byte의 영역을 차지하게됩니다. (참고로 1byte = 8bit)

 

문자: char, 1byte, format %c

문자열 char[size] size만큼의 바이트 문자열, format %s 

 

A	l	g	o	r	i	t	h	m	NULL('\0')
arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	arr[6]	arr[7]	arr[8]	arr[9]

 

위에 String형태는 다음과 같이 나타낼 수 있습니다.

 

char arr[10] ="Algorithm";
string arr = "Algorithm";

두개의 의미는 같은 문자열을 의미하게 됩니다.  하지만, string을 사용하게 되면 'A'과 같이 char형식으로 생성이 불가능합니다.

이것을 가능하게 하려면 

 

string arr;
arr = "Algorithm";

의 형식으로 작성해주어야 합니다.

 

자 그러면, 문자열의 형태가 어떻게 되었는지 살펴보았으니 위에서 사용한 string이 과연 무엇일까요?

보통 C언어에서는 위의 문자열을 출력하기 위해서는

char[10] arr = "Algorithm";
printf("%s",arr);

이 형식으로 문자열을 출력했었죠?

 

하지만 C++에서는 std::string을 지원합니다. 그리고 printf("%s",arr); 과 같이 출력형식을 사용하지 않고 간편하게 사용할 수 있는 방법이 있습니다.

바로 C++ 언어에서는 단일 글로벌 네임스페이스를 제공합니다. 네임 스페이스를 사용하기 위해서는 C언어 헤더부분에 using namespace std; 를 선언해주게 됩니다. 

 

# 그러면 네임 스페이스(Namespace)란 무엇일까요?

namespace란 모든 식별자(변수,함수,형식 등의 이름)가 고유하도록 보장하는 코드영역을 정의합니다.

 

 

* 참고 사항으로 코딩테스트때 string을 입력을 받게 되는 경우가 있는데요.

예를 들어 string 문자열 배열로 입력을 받아야하는데

TEST CASE

ABCD

와 같이 입력을 받게 된다면 ABCD를 String으로 인식해버리기 때문에 

 

#include <iostream>
using namespace std;
string str[10];
for(int i=0; i<str.size(); i++){
cin >> s[i]
}

잘못된 형식으로 입력을 받게 되는 경우가 있습니다.

↓

#include <iostream>
using namespace std;
string str[10];
for(int i=0; i<str.size(); i++){
scanf("%1c",str[i]);
}

형식으로 입력을 받게된다면 붙어있는 문자열도 string 문자열 배열안에 넣을 수 있습니다.

 

※다만 시간복잡도를 입력부분에서 시간초과가 날 수 있다는점을 고려해주셔야 합니다.

---

이제 그러면 본격적으로 STL std::string에 대해서 알아보겠습니다.

# STL std::string 멤버 타입

value_type	char
traits_type	char_traits<char>
allocator_type	allocator<char>
reference	char&
const_reference	const char&
pointer	char*
const_pointer	const char*
iterator	a random access iterator to char (convertible to const_iterator)
const_iterator	a random access iterator to const char
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
difference_type	ptrdiff_t
size_type	size_t

 

# Member functions

#1 str.at(index)

함수 원형 : char& at (size_t index);

함수 설명 : index 숫자, 해당 위치(n)에 해당하는 문자를 반환( index = 0 시작)

함수 예시 : str.at(0);    // '0번째 인자를리턴합니다.

 

#2 str.operator[index]

함수 원형 : char& operator[](size_t index);

함수 설명 : C++ string은 일반 배열처럼 대괄호를 이용해서 string 인자에 접근

  at과 다른점은 string의 index범위를 검사하지 않기 때문에 at 함수보다는 빠릅니다. 

index=0 시작, index 번째 인자를 반환

함수 예시 : str[1];    //1번째 인자를 리턴

 

#3 str.front();

함수 원형 : char& front();

함수 설명 : C++11, string의 맨 앞 인자를 반환

함수 예시 : str.front();    // string 맨 앞글자 반환

 

#4 str1.back();

함수 원형 : char& back();

함수 설명 : C++11부터 가능합니다. string의 맨 뒤 인자를 반환합니다

함수 예시 : str.back();    //'K'를 리턴합니다.

 

#5 str1.size();

함수 원형 : size_t size() const;

함수 설명 : string의 사이즈를 반환합니다.

함수 예시 : str.size();    // 문자열 사이즈 반환

 

#6 str.length();

함수 원형 : size_t length() const;

함수 설명 : string의 길이를 반환합니다. size() 함수와 같다고 생각하면 됩니다.

함수 예시 : str.length();    // 문자열 길이 반환

 

#7 str.capacity();

함수 원형 : size_t capacity() const;

함수 설명 : string 객체에 할당된 메모리 크기(bytes)를 반환합니다. 

  capacity는 vector의 capacity와 마찬가지로 스트링 길이가 증가할 수 있기 때문에, 메모리 할당을 size에 대비해서 여유롭게 합니다. 

  size가 capacity를 넘게 될때 새롭게 더 큰 capacity(메모리)를 할당

함수 예시 : str.capacity();    // "HelloWorld" 길이는 11인데 capacity는 문자열보다 많은 메모리양 할당

 

#8 sr.resize(n);

함수 원형 : void resize (size_t n);

함수 원형 : void resize (size_t n, char c);

함수 설명 : string을 n만큼의 크기로 만듭니다. 

  만약 그 크기가 원래 사이즈 보다 작다면, 남은 스트링을 버립니다. 

  만약 그 크기가 원래 사이즈 보다 크다면, 빈 공간으로 남은 공간을 채웁니다. 만약 c를 사용한다면 남은 공간을 c로 채울 수 있습니다.

함수 예시 : str.resize(5)    // size 5만큼 재할당 (문자열)

 

#9 str.shrink_to_fit();

함수 원형 : void shrink_to_fit();

함수 설명 : C++11 입니다. 이 함수는 스트링 길이에 비해 낭비되고 있는 capacity(메모리)를 줄이는 함수입니다. 

함수 예시 : str.shrink_to_fit();  // capacity에 메모리적으로 여유로 할당하였던것들을 기존의 메모리 크기대로 할당

 

#10 str.reserve(n);

함수 원형 : void reserve(size_t n = 0);

함수 설명 : 문자열을 알맞은 capacity를 할당 함수

 

#11 str.clear();

함수 원형 : void clear();

함수 설명 : 스트링에 들어있는 문자열을 지우는 함수입니다. 이때, size와 length는 0이 되고, capacity는 그대로 남게 됩니다.

함수 예시 : str.clear();  (메모리 해제가 아닌 문자열 값들을 삭제하는것 capacity는 그대로)

 

#12 str.empty();

함수 원형 : bool empty() const;

함수 설명 : 스트링이 비었는지 확인하는 함수입니다. 비었으면 true, 아니면 false

함수 예시 : if(str.empty())

 

#13 str.c_str()

함수 원형 : const char* c_str() const;

함수 설명 : C++ 스타일의 string 문자열을 C스타일의 문자열로 변경해주는 함수입니다. 

함수 예시 : const char* arr = str.c_str();    // "문자열"가 "문자열\0"로 반환

 

#14 str.substr(....)

함수 원형 : string substr(size_t index = 0, size_t len = npos) const;

함수 설명 : string을 index 에서부터 len만큼 잘라서 반환하는 함수

함수 예시 : str.ubstr();         // 문자열 그대로

함수 예시 : str.substr(5);        // index 5부터 end

함수 예시 : str.substr(5, 1);     // index 5부터 1까지

 

#15 str.replace(....)

함수 원형 : string& replace(size_t index, size_t len, const string& str)

함수 설명 : 함수를 호출하는 문자열의 index위치에서 len 길이까지의 범위를 매개변수로 들어온 str 전체로 대체 하는 함수

함수 예시 : str1.replace(5, 2, str2); (parameter1 = index, parameter2 = size, parameter3 = string

 

#16 str.compare(....)

함수 원형 : int compare(const string& str) const;

함수 원형 : int compare(size_t index, size_t len, const string& str) const;

함수 설명 : 매개변수로 들어온 str을 비교해서 같으면 0을 반환하고, 다르면 0이 아닌 값을 반환하는 함수입니다.

  호출하는 스트링의 값이 매개변수로 들어온 스트링의 값보다 작을때(사전순 빠를때) 음수(-1)를 반환하고

  호출하는 스트링의 값이 매개변수로 들어온 스트링의 값보다 클때(사전순 느릴때) 양수(1)를 반환합니다

 

함수 예시 : str1.compare("HelloWorld");    //이 경우에는 두 스트링이 같기 때문에 0을 반환합니다.

함수 예시 : str1.compare(0, 2, str2);    // index 0~2 str2 비교

 

#17 str.copy(....)

함수 원형 : size_t copy(char* arr, size_t len, size_t index = 0) const;

함수 설명 : 딱봐도 복사를 하는 함수입니다. 이거는 특이하게 길이는 나타내는 len이 두번째고, index가 세번째 인자

  두번째 매개변수는 복사할 문자열의 길이를 나타냅니다.

  세번째 매개변수는 복사를 시작할 위치 입니다. 

  마지막으로 실제로 복사된 길이, arr의 길이를 반환합니다.

함수 예시 : char arr[10];    //문자열을 복사해서 넣을 빈 배열을 만듭니다.

함수 예시 : int arrLen = str1.copy(arr, 3, 5);    //5번째 index부터 3의 길이만큼 복사 한다는 거니까 "BlockDMask" 빨간 부분이 들어갔을겁니다. 그리고 반환하는 arrLen은 3의 길이겠죠?

함수 예시 : arr[arrLen] = '\0';    //그리고 C의 문자열의 끝에는 '\0' 추가

 

#18 str.find(....)

함수 원형 : size_t find (const string& str, size_t index = 0) const;

함수 원형 : size_t find (const char* arr, size_t index = 0) const;

함수 설명 : 매개변수로 들어온 문자열과, 내 문자열중에 일치하는 게 있는지 확인하는 함수

  만약에 일치하는게 있다면, 일치하는 부분의 첫번째 순서(index)를 반환합니다.

  두번째 매개변수로 들어온 index는 어느 위치에서 부터 찾을까 입니다.

함수 예시 : str.find("hello");    // 0 을 반환합니다.

함수 예시 : str.find("hello", 5);    // 찾은 위치 반환

 

#19 str.push_back(c)

함수 원형 : void push_back(char c);

함수 설명 : 함수를 호출하는 스트링의 맨뒤에 문자 c를 더하는 함수

함수 예시 : str.push_back('a');   // string push back()

 

#20 str.pop_back()

함수 원형 : void pop_back()

함수 설명 : 함수를 호출하는 스트링의 맨뒤에 있는 문자 하나를 없애는 함수

함수 예시 : str1.pop_back();    // string pop back()

 

#21 str.begin();

함수 원형 : iterator begin();

함수 원형 : const_iterator begin() const;

함수 설명 : 문자열의 첫 번째 문자를 가리키는 반복자(iterator 포인터)를 반환합니다.

 

#22 str.end();

함수 원형 : iterator end();

함수 원형 : const_iterator end() const;

함수 설명 : 문자열의 마지막의 바로 다음을 가리키는 반복자(iterator 포인터)를 반환합니다. 

 

#23 swap(str1, str2);

함수 원형 : void swap(string& str1, string& str2);

함수 설명 : str1과 str2 교체

  스왑을 할때 복사를 해서 스왑을 하는것이 아니라 서로 참조(reference)를 교환해서 스왑을 합니다. 

  그렇기 때문에 복사에 의한 성능저하를 우려할 필요가 없습니다.

함수 예시 : swap(str1, str2);    // Swap

 

#24 operator+

함수 설명 : 오퍼레이터 +인데요. string 이어 붙이기

함수 예시 : str1 += str2;  // str1 + str2 문자 이어서 붙이기

 

#25 str1.append(str2)

함수 설명: string 문자열 붙이기 

함수 예시: str.append("문자열"); // str1 += str2; 같은 원리로 동작한다.

 

#26 str1.assign(str2);

함수 설명: 해당 변수에 문자열을 할당(변수 정의)

함수 예시: str1.assign(str2);

 

#27 to_string: int to string

함수 설명: int 변수를 string 변수로 변환

함수 예시: string str = to_string(정수형);

 

#28 atoi: string to int

함수 설명: string 변수를 int변수로 변환

함수 예시: int number = atoi(str.c_str()); // atoi 매개 변수가 char* 이므로 c_str()함수를 사용하여 변환

 

#29 reverse()

함수 설명: 문자열을 역순으로 뒤집는다.

함수 예시: string str = "hello world"; reverse(str.begin(),str.end());

 

 

 

//
//  std::string.cpp
//  beakjoon_algorithm
//
//  Created by kgh on 03/07/2019.
//  Copyright © 2019 kgh. All rights reserved.
//
#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string str = "Hello World";     // string str("HelloWorld");   같은 형식
    string str_copy = "Coding";
    str.push_back('!');
    cout << str << '\n';
    str.pop_back();
    str += str_copy;
    cout << str << '\n';
    cout << str.size() << '\n';
    cout << str.length() << '\n';
    cout << str.capacity() << '\n';
    str.resize(4);
    cout << str << '\n';
    cout << str.size() << '\n';
    cout << str.length() << '\n';
    cout << str.capacity() << '\n';
    str.shrink_to_fit();
    cout << str << endl;
    cout << str.size() << '\n';
    cout << str.length() << '\n';
    cout << str.capacity() << '\n';
    cout << str.substr(3) << '\n';
    cout << str.substr(3,1) << '\n';
    cout << str.replace(3, 2, str_copy) << '\n';
    cout << str.find("Hello") << '\n';
    cout << str.find("Hello", 4) << '\n';
    cout << str[str.size() - 1] << '\n';
    cout << str.at(0) << '\n';
    cout << str[0] << '\n';
    cout << str.at(0) << '\n';
    cout << str.front() << '\n';
    cout << str.back() << '\n';
    string::iterator iter = str.begin();
    for (; iter != str.end(); ++iter)
    {
        cout << *iter << " ";
    }
    char arr[10];
    int arr_size = str.copy(arr, 3, 5);
    arr[arr_size] = '\0';
    cout << arr << '\n';
    cout << str.compare(str_copy) << '\n';
    str.clear();
    return 0;
}

 

 

이런식으로 코드를 사용한다는것만 알고계시고, 필요할때 마다 보면서 쓰려고 정리하게 되었습니다.

 

Reference: https://blockdmask.tistory.com/338

참고하여 작성하였습니다.