[백준 2941][C++] 크로아티아 알파벳, segfault, size_t

https://www.acmicpc.net/board/view/122419#post

글 읽기 - 문제는 풀었지만, segfault가 나옵니다.

---

◆문제의 시작
문제에 대한 로직을 작성하고 제출하니 90%에서 segfault가 나왔다.

하지만 아무리 생각해도 범위 밖을 나가지 않았다고 생각해 백준에 질문을 올렸다.

 

●아래는 코드 전문이다.

#include <iostream>
#include <string>

int main()
{
    std::string array;
    getline(std::cin, array);
    int answer = array.size();

	//문자열을 검사한다.
    for (int i = 0; i < array.size() - 1; i++)
    {
    	//2글자로 이루어진 크로아티아 알파벳을 발견시 길이에서 1을 뺀다.
        if (array[i] == 'l' || array[i] == 'n')
        {
            if (array[i + 1] == 'j')
            {
                answer--;
            }
        }
        if (array[i] == 'c' || array[i] == 'z' || array[i] == 's')
        {
            if (array[i + 1] == '=')
            {
                answer--;
            }
        }
        if (array[i] == 'c' || array[i] == 'd')
        {
            if (array[i + 1] == '-')
            {
                answer--;
            }
        }
    }
    for (int i = 0; i < array.size() - 2; i++)
    {
    	//3글자로 이루어진 크로아티아 알파벳을 발견시 위에서 1을 빼주었기 때문에 길이에서 1만 뺀다.
        if (array[i] == 'd')
        {
            if (array[i + 1] == 'z')
            {
                if (array[i + 2] == '=')
                {
                    answer--;
                }
            }
        }
    }
    std::cout << answer;
}

 

◆해결

몇 분 안되서 답변이 작성되었는데, string의 size() 함수의 리턴값이 typedef usigned long long size_t; (64비트)라서 언더플로우를 통해 무한 루프를 돌게 된다는 답변을 받았다.

메모리의 저장공간을 나타내는 size_t 자료형은 해당 시스템에서  어떤 객체나 값이 포함할 수 있는 최대 크기의 데이터를 표현하는 타입으로 반드시 unsigned 형으로 나타낸다.

테스트 케이스로 하나의 단어만 들어갈 경우 아래의 부분에서 i < 18446744073709551615(1 - 2) 가 되버리는 것이다.

for (int i = 0; i < array.size() - 2; i++)

그렇게 무한루프를 돌순 있지만 18446744073709551615이라는 비정상적인 크기를 감당할 수 없어 에러가 난것이다.

 

위의 반복문에서 -2는 문자열을 확인할때 i기준으로 뒤에 두자리까지 확인하기 때문에 Out of Array를 걱정해서 넣어 줬는데, 정작 -2를 안해주어도 쓰레기값을 검사해서 오류가 나진 않았다.

그 쓰레기값 조차 d 다음 z 다음 = 을 만족을 시키긴 천문학적으로 어렵기 때문에 백준에서도 답 처리 되었다.

 

◆결론

size_t는 unsigned 자료형이며 해당 시스템에서  어떤 객체나 값이 포함할 수 있는 최대 크기의 데이터를 표현하는 타입이다.

※size_t와 size_type은 C++에서 같다.

 

●아래 코드는 size 함수를 int형인 answer에 넣어 암시적 형변환을 시켜주어 해결하였다.

#include <iostream>
#include <string>

int main()
{
    std::string array;
    getline(std::cin, array);
    int answer = array.size();

    for (int i = 0; i < array.size() - 1; i++)
    {
        if (array[i] == 'l' || array[i] == 'n')
        {
            if (array[i + 1] == 'j')
            {
                answer--;
            }
        }
        if (array[i] == 'c' || array[i] == 'z' || array[i] == 's')
        {
            if (array[i + 1] == '=')
            {
                answer--;
            }
        }
        if (array[i] == 'c' || array[i] == 'd')
        {
            if (array[i + 1] == '-')
            {
                answer--;
            }
        }
    }
    for (int i = 0; i < array.size() - 2; i++)
    {
        if (array[i] == 'd')
        {
            if (array[i + 1] == 'z')
            {
                if (array[i + 2] == '=')
                {
                    answer--;
                }
            }
        }
    }
    std::cout << answer;
}