[bj 10809] c++ 풀이 -> 문자열 동적할당 직접 구현하기

https://www.acmicpc.net/problem/10809

#include<iostream>
#include<string>
using namespace std;

int main(int argc, char** argv)
{
    int cnt[26] = { 0 , };
	string s;
    
	cin >> s;

	for (char i = 'a'; i <= 'z'; i++) {
		cout << (int)s.find(i) << ' '; // find의 return type은 unsigned형이라서 2의 보수에 의해 최대 크기 양수값이 출력된다.
	}

    return 0;
}

코드 출처 : https://cryptosalamander.tistory.com/11

std::string과 std::find를 사용하면 쉽게 구현할 수 있는데, string을 문자열 동적할당을 이용해서 직접 구현해보았다.

 

#include<iostream>
using namespace std;

// 문자열의 길이를 반환하는 함수
int slen(const char* str) 
{
    int index = 0;
    while ( str[index] != '\0')
    {
       ++index;
    }
    return index;
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // ret은 a~z 까지 중에 찾은 글자의 첫번째 인덱스를 저장해둘 배열이고 -1로 초기화했다.
    int ret[26];
    for (int i = 0; i<(sizeof(ret)/sizeof(*ret)); ++i)
    {
        ret[i] = -1;
    }
    
    // 임시로 저장해둘 문자열
    char buffer[1024];
    cin.getline(buffer,sizeof(buffer));
    cin.ignore();
    
    // 입력 받은 문자열의 길이를 계산
    int length = slen(buffer);
    
    // 문자열 동적할당 
    char* s = new char[length+1]; // +1은 \null 문자 때문
    
    // 동적할당된 문자열 초기화
    for(int i=0; i<=length; ++i)
    {
        s[i]=buffer[i];
    }
    
    // 인덱스를 ret에 저장하는 부분 구현 
    for(int i =0; i<=length; ++i)
    {
        int tmp = s[i]-'a';
        if (ret[tmp] == -1)
        {
            ret[tmp] = i;
        }
    }
    
    // ret 출력
    for(int i=0; i<26; ++i)
    {
        cout << ret[i];
        if (i != 25) cout <<' ';
    }
    
    // 동적할당 해제
    delete[] s;
   
    return 0;
}

 

위 코드를 하나하나 뜯어보자.

// ret은 a~z 까지 중에 찾은 글자의 첫번째 인덱스를 저장해둘 배열이고 -1로 초기화했다.
    int ret[26];
    for (int i = 0; i<(sizeof(ret)/sizeof(*ret)); ++i)
    {
        ret[i] = -1;
    }

여기서는 std::find함수를 안 쓰기 위해서  입력된 문자에서 첫 번째로 찾은 a~z의 문자에 대해 그 인덱스를 저장해둘 배열을 구현했다. 예를 들어 c를 찾아보자고 하자. 입력 받은 문자들에서 c의 인덱스가 5라고 한다면, ret[2]=5 로 저장한다.

 

sizeof(ret)은 ret 배열이 차지하는 전체 byte이다. char형이므로 1byte * 26 = 26 byte이고,

sizeof(*ret)은 *이 간접참조연산자이므로 ret 배열의 첫 번째 요소를 가르키고, 그 크기를 반환한다. (*ret은 ret[0]과 같다) 배열의 첫 번째 요소의 크기는 1byte이다. 

즉, sizeof(ret)/sizeof(*ret)은 배열의 길이를 의미한다.

 

    // 임시로 저장해둘 문자열
    char buffer[1024];
    cin.getline(buffer,sizeof(buffer));
    cin.ignore();
    int length = slen(buffer);

동적할당을 하기 위해서는 배열의 사이즈를 알아야 하는데, 크게 두 가지 방법으로 구현할 수 있을 것이다.

 

1. buffer라는 임시 배열을 선언하는 방식을 통해 문자열의 사이즈를 계산하여 동적할당을 구현하는 방법. 만약 buffer에 입력되는 문자열의 길이가 초기화된 사이즈를 초과하면 문자열이 잘리는 문제가 발생할 것이다. 그렇다고 buffer라는 임시 변수의 길이를 크게 잡아놓으면 쓸데없이 메모리를 잡아먹고 있는 것이다. 

 

2. 동적할당 사이즈를 적당히 작은 숫자로 초기화해준 뒤에 문자 하나하나를 입력받아서 동적할당된 배열에 넣다가, 동적할당 사이즈를 초과할 시 사이즈를 +1한 새로운 동적할당 배열을 생성하고 기존의 동적할당된 배열을 해제하는 방식으로 구현할 수 있을 것이다. 할당과 해제를 반복해야하므로 문자열이 길어진다면 오버헤드가 발생할 것이다.

 

첫 번째 방식이 구현이 더 쉬우므로 첫 번째 방식으로 구현해보았다.

 

위 코드는 문자열을 받기 위해 임시 변수 buffer를 선언한 것이다.

총 길이 1024 만큼의 문자열을 받을 수 있다.(문제에서 얼마나 긴 길이의 문자열이 입력되는지 모르므로 일단 임의로 숫자를 정해주었다. 1024 길이 이상의 문자열이 입력될 경우 논리적 오류를 범하는 것이다.)

 

// 문자열의 길이를 반환하는 함수
int slen(const char* str) 
{
    int index = 0;
    while ( str[index] != '\0')
    {
       ++index;
    }
    return index;
}

...

	// 입력 받은 문자열의 길이를 계산
    int length = slen(buffer);
    
    // 문자열 동적할당 
    char* s = new char[length+1]; // +1은 \null 문자 때문
    
    // 동적할당된 문자열 초기화
    for(int i=0; i<=length; ++i)
    {
        s[i]=buffer[i];
    }

 

문자열을 계산해주는 함수를 직접 구현했고, 함수를 통해 구한 입력받은 문자열 길이에 +1 해서 동적할당 사이즈로 설정한다.

    // 인덱스를 ret에 저장하는 부분 구현 
    for(int i =0; i<=length; ++i)
    {
        int tmp = s[i]-'a';
        if (ret[tmp] == -1)
        {
            ret[tmp] = i;
        }
    }
    
    // ret 출력
    for(int i=0; i<26; ++i)
    {
        cout << ret[i];
        if (i != 25) cout <<' ';
    }
    
    // 동적할당 해제
    delete[] s;

나머지 부분은 std::find를 대체해서 인덱스를 찾는 과정을 구현한 것이다.

 

마지막에 동적할당을 해제해준다.

string은 동적할당과 소멸자(객체의 동적할당을 해제해주는 메소드, ~연산자로 표현한다.)를 string 클래스 내부에 구현해놓았다.

그래서 string으로 생성된 객체는 main 함수를 벗어나거나 스코프를 벗어나면 알아서 소멸자가 호출되면서 동적할당 해제가 수행된다.

 

여기서는 필요한 부분에 대해서만 string 클래스를  구현했는데, 실제 string의 모든 기능을 구현해보는 것도 좋을 것 같다. 아래 블로그 글을 참고하자.

https://samdo0812.tistory.com/30