선밥의 공부하는 블로그

크기가 작은 부분 문자열

문제 링크

크기가 작은 부분 문자열

분석

문자열 t에서 p의 길이만큼 부분 문자열을 구하고, 정수로 변환한 다음 숫자를 비교하는 문제입니다.

부분 문자열을 차례대로 추출해야하므로 반복문을 사용합니다.
반복문 i번째부터 p의 길이만큼 부분 문자열을 구해야합니다.
부분 문자열은 t의 substr멤버함수를 사용하면 됩니다.

문제의 제한사항에서 t와 p의 길이가 18까지 가능하므로 int자료형으로 표현할 수 없습니다.
long long을 사용해야합니다.

풀이

#include <string>

int solution(std::string t, std::string p) {
    int answer = 0;
    long long pNum = std::stoll(p);
    
    for (int i = 0; i <= t.length() - p.length(); ++i)
    {
        std::string str = t.substr(i, p.length());
        long long tNum = std::stoll(str);
        
        if (tNum <= pNum)
        {
            ++answer;
        }
    }
    
    return answer;
}

substr함수는 첫 매개변수의 인덱스부터 두번째 매개변수의 갯수만큼 문자열을 구합니다.

반복문의 조건에 t.length() - p.length()를 하는 이유는 t문자열 뒷부분에서 p의 문자열 길이만큼 부분 문자열을 구할 수 없는 경우를 제외하기 위함입니다.

학습의 용도로 STL함수를 사용하지 않고 풀어보았습니다.

#include <string>

int solution(std::string t, std::string p) {
    int answer = 0;
    long long pNum = 0;
    
    for (int i = 0; i < p.length(); ++i)
    {
        pNum *= 10;
        pNum += static_cast<int>(p[i]) - '0';
    }
    
    for (int i = 0; i <= t.length() - p.length(); ++i)
    {
        long long tNum = 0;
        
        for (int j = 0; j < p.length(); ++j)
        {
            tNum *= 10;
            tNum += static_cast<int>(t[i + j]) - '0';
        }
                
        if (tNum <= pNum)
        {
            ++answer;
        }
    }
    
    return answer;
}

문자열에서도 비교연산자를 사용할 수 있는데, 이 경우 사전순 비교로 동작합니다.
두 문자열의 길이가 동일하므로 숫자 크기를 비교하는 것과 같은 결과를 얻을 수 있습니다.

#include <string>

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

성능 요약

STL함수를 사용한 성능입니다.

테스트 1 〉 통과 (0.24ms, 4.17MB)
테스트 2 〉 통과 (0.25ms, 4.13MB)
테스트 3 〉 통과 (0.20ms, 4.21MB)
테스트 4 〉 통과 (0.19ms, 3.68MB)
테스트 5 〉 통과 (0.20ms, 4.21MB)
테스트 6 〉 통과 (0.22ms, 4.21MB)
테스트 7 〉 통과 (0.75ms, 4.21MB)
테스트 8 〉 통과 (0.13ms, 4.15MB)
테스트 9 〉 통과 (0.12ms, 4.14MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)
테스트 11 〉 통과 (0.30ms, 3.68MB)
테스트 12 〉 통과 (0.76ms, 3.68MB)
테스트 13 〉 통과 (0.58ms, 4.2MB)
테스트 14 〉 통과 (0.31ms, 4.13MB)
테스트 15 〉 통과 (0.23ms, 4.14MB)
테스트 16 〉 통과 (0.26ms, 4.2MB)
테스트 17 〉 통과 (0.56ms, 4.01MB)
테스트 18 〉 통과 (0.34ms, 4.14MB)
테스트 19 〉 통과 (0.08ms, 4.15MB)
테스트 20 〉 통과 (0.06ms, 4.14MB)
테스트 21 〉 통과 (0.01ms, 4.21MB)
테스트 22 〉 통과 (0.04ms, 4.2MB)
테스트 23 〉 통과 (0.11ms, 4.16MB)
테스트 24 〉 통과 (0.01ms, 4.15MB)
테스트 25 〉 통과 (0.01ms, 4.21MB)
테스트 26 〉 통과 (0.01ms, 4.2MB)
테스트 27 〉 통과 (0.02ms, 4.16MB)
테스트 28 〉 통과 (0.01ms, 4.21MB)
테스트 29 〉 통과 (0.01ms, 4.14MB)
테스트 30 〉 통과 (0.07ms, 4.21MB)
테스트 31 〉 통과 (0.01ms, 4.14MB)
테스트 32 〉 통과 (0.01ms, 3.68MB)
테스트 33 〉 통과 (0.01ms, 4.12MB)
테스트 34 〉 통과 (0.01ms, 3.68MB)
테스트 35 〉 통과 (0.01ms, 4.14MB)
테스트 36 〉 통과 (0.01ms, 4.21MB)
테스트 37 〉 통과 (0.01ms, 4.14MB)
테스트 38 〉 통과 (0.01ms, 3.68MB)

학습의 용도로 STL함수를 사용하지 않은 성능입니다.

테스트 1 〉 통과 (0.02ms, 4.14MB)
테스트 2 〉 통과 (0.04ms, 4.19MB)
테스트 3 〉 통과 (0.04ms, 4.16MB)
테스트 4 〉 통과 (0.03ms, 4.14MB)
테스트 5 〉 통과 (0.03ms, 4.2MB)
테스트 6 〉 통과 (0.03ms, 4.14MB)
테스트 7 〉 통과 (0.07ms, 4.16MB)
테스트 8 〉 통과 (0.02ms, 4.13MB)
테스트 9 〉 통과 (0.01ms, 4.16MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)
테스트 11 〉 통과 (0.03ms, 3.92MB)
테스트 12 〉 통과 (0.08ms, 4.21MB)
테스트 13 〉 통과 (0.06ms, 4.13MB)
테스트 14 〉 통과 (0.03ms, 4.02MB)
테스트 15 〉 통과 (0.03ms, 3.67MB)
테스트 16 〉 통과 (0.03ms, 4.01MB)
테스트 17 〉 통과 (0.06ms, 4.27MB)
테스트 18 〉 통과 (0.03ms, 4.21MB)
테스트 19 〉 통과 (0.01ms, 3.67MB)
테스트 20 〉 통과 (0.01ms, 4.21MB)
테스트 21 〉 통과 (0.01ms, 4.14MB)
테스트 22 〉 통과 (0.01ms, 4.02MB)
테스트 23 〉 통과 (0.01ms, 4.2MB)
테스트 24 〉 통과 (0.01ms, 4.2MB)
테스트 25 〉 통과 (0.01ms, 3.59MB)
테스트 26 〉 통과 (0.01ms, 4.17MB)
테스트 27 〉 통과 (0.01ms, 4.2MB)
테스트 28 〉 통과 (0.01ms, 4.14MB)
테스트 29 〉 통과 (0.01ms, 4.16MB)
테스트 30 〉 통과 (0.01ms, 4.21MB)
테스트 31 〉 통과 (0.01ms, 4.07MB)
테스트 32 〉 통과 (0.01ms, 4.19MB)
테스트 33 〉 통과 (0.01ms, 4.21MB)
테스트 34 〉 통과 (0.01ms, 4.2MB)
테스트 35 〉 통과 (0.01ms, 3.65MB)
테스트 36 〉 통과 (0.01ms, 4.27MB)
테스트 37 〉 통과 (0.01ms, 4.14MB)
테스트 38 〉 통과 (0.01ms, 4.16MB)

문자열에 비교연산자를 사용한 성능입니다.

테스트 1 〉 통과 (0.13ms, 4.13MB)
테스트 2 〉 통과 (0.11ms, 3.63MB)
테스트 3 〉 통과 (0.08ms, 4.21MB)
테스트 4 〉 통과 (0.07ms, 4.21MB)
테스트 5 〉 통과 (0.06ms, 4.21MB)
테스트 6 〉 통과 (0.09ms, 4.14MB)
테스트 7 〉 통과 (0.12ms, 4.11MB)
테스트 8 〉 통과 (0.06ms, 4.14MB)
테스트 9 〉 통과 (0.05ms, 4.14MB)
테스트 10 〉 통과 (0.01ms, 4.16MB)
테스트 11 〉 통과 (0.09ms, 4.21MB)
테스트 12 〉 통과 (0.12ms, 4.14MB)
테스트 13 〉 통과 (0.09ms, 4.2MB)
테스트 14 〉 통과 (0.07ms, 4.21MB)
테스트 15 〉 통과 (0.13ms, 4.16MB)
테스트 16 〉 통과 (0.06ms, 4.24MB)
테스트 17 〉 통과 (0.09ms, 3.6MB)
테스트 18 〉 통과 (0.18ms, 4.2MB)
테스트 19 〉 통과 (0.04ms, 4.21MB)
테스트 20 〉 통과 (0.03ms, 4.19MB)
테스트 21 〉 통과 (0.01ms, 4.14MB)
테스트 22 〉 통과 (0.01ms, 3.67MB)
테스트 23 〉 통과 (0.02ms, 4.21MB)
테스트 24 〉 통과 (0.01ms, 4.15MB)
테스트 25 〉 통과 (0.01ms, 4.15MB)
테스트 26 〉 통과 (0.01ms, 4.14MB)
테스트 27 〉 통과 (0.01ms, 4.44MB)
테스트 28 〉 통과 (0.01ms, 4.14MB)
테스트 29 〉 통과 (0.01ms, 4.21MB)
테스트 30 〉 통과 (0.02ms, 4.21MB)
테스트 31 〉 통과 (0.01ms, 4.14MB)
테스트 32 〉 통과 (0.01ms, 4.14MB)
테스트 33 〉 통과 (0.01ms, 4.2MB)
테스트 34 〉 통과 (0.01ms, 4.21MB)
테스트 35 〉 통과 (0.01ms, 4.16MB)
테스트 36 〉 통과 (0.01ms, 3.72MB)
테스트 37 〉 통과 (0.01ms, 4.2MB)
테스트 38 〉 통과 (0.01ms, 4.15MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글