[프로그래머스] 크기가 작은 부분문자열

문제 설명

숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.

예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.

 

풀이 + 코드 (with GPT)

처음에 짠 코드가 주어진 예시 문제를 잘 풀었지만 제출하려고 하면 (signal: aborted (core dumped)) 오류가 발생하는 문제가 있었다.

// 처음 코드
#include <string>
#include <vector>

using namespace std;

int solution(string t, string p) {
    int answer = 0;
    
    for (int i=0; i<t.length()-p.length()+1; i++){
        if(stoi(t.substr(i, p.length())) <= stoi(p)){
            answer++;
        }
    }
    
    return answer;
}

그 원인을 찾는데 GPT에게 도움을 구해 5가지 답변을 받았다.

1. 입력 문자열에 공백이나 잘못된 문자가 포함되어 있는 경우
2. 숫자가 너무 큰 경우
3. t의 길이가 p의 길이보다 작은 경우
4. t와 p의 길이가 0인 경우
5. t에 "0"으로 시작하는 부분 문자열이 포함된 경우

하지만 제한사항에 따르면 1,3,4,5의 경우는 아님을 확인했다.

제한 사항
1 ≤ p의 길이 ≤ 18
p의 길이 ≤ t의 길이 ≤ 10,000
t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

숫자가 너무 큰 경우? stoi 함수는 정수 범위 내의 숫자를 처리합니다. 따라서 입력값이 너무 큰 경우에는 std::out_of_range 예외를 발생시킬 수 있습니다. 입력값의 범위를 확인하고 필요한 경우 long long과 같은 큰 자료형을 사용하여 처리해야 합니다.

완전 유레카! 생각지도 못 했던 오류였다!

int 값의 범위는 –2,147,483,648 ~ 2,147,483,647,
long long 값의 범위는9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 (짱 크다)

이보다 더 큰 long long을 사용하여 코드를 수정했다.

// 수정된 코드
#include <string>
#include <vector>

using namespace std;

int solution(string t, string p) {
    int answer = 0;
    
    for (int i=0; i<t.length()-p.length()+1; i++){
        long long numT = stoll(t.substr(i, p.length()));
        long long numP = stoll(p);
        
        if(numT <= numP){
            answer++;
        }
    }
    
    return answer;
}

번외로 GPT가 풀었을 때 코드도 두고 갑니다.

// GPT가 푼 코드
#include <string>
#include <vector>

using namespace std;

int solution(string t, string p) {
    int answer = 0;
    int lenT = t.length();
    int lenP = p.length();

    for (int i = 0; i <= lenT - lenP; i++) {
        bool isSmallerOrEqual = true;
        for (int j = 0; j < lenP; j++) {
            if (t[i + j] > p[j]) {
                isSmallerOrEqual = false;
                break;
            } else if (t[i + j] < p[j]) {
                break;
            }
        }

        if (isSmallerOrEqual) {
            answer++;
        }
    }

    return answer;
}