[2025.01.14] 크기가 작은 부분 문자열

문제 설명

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

 

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

 

 

제한사항

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

 

 

입출력 예

t			p	result	설명
"3141592"			"271"	2	본문과 같습니다.
"500220839878"			"7"	8	p의 길이가 1이므로 t의 부분문자열은 "5", "0", "0", "2", "2", "0", "8", "3", "9", "8", "7", "8"이며 이중 7보다 작거나 같은 숫자는 "5", "0", "0", "2", "2", "0", "3", "7" 이렇게 8개가 있습니다.
"10203"			"15"	3	p의 길이가 2이므로 t의 부분문자열은 "10", "02", "20", "03"이며, 이중 15보다 작거나 같은 숫자는 "10", "02", "03" 이렇게 3개입니다. "02"와 "03"은 각각 2, 3에 해당한다는 점을 주의하세요.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>

using namespace std;

int solution(string t, string p) {
    int answer = 0;
    
    // 문자열 길이 구하기
    int p_length=p.length();
    int t_length=t.length();
    
    // 문자열 추출하여 비교하기
    for(int i=0; i<t_length-p_length+1; i++)
    {
        long sub_t = stol(t.substr(i, p_length)); // p와 길이가 같은 부분 문자열
        
        // p보다 작거나 같다면
        if(sub_t<=stol(p))
        {
            answer++; // answer 1 증가
        }
    }
    
    return answer;
}

먼저 p와 t의 문자열의 길이를 구한다. 이제 p의 길이 만큼 t를 일부 잘라내여 계속 p의 값과 비교해야 한다. for문을 이용하여 반복문을 돌며 이 작업을 수행해준다.

 

for문이 돌아가는 횟수는 t_length-p_length+1이다. 반복문을 돌면서 substr 함수를 이용해 문자열의 일부를 p_length만큼 잘라와 stol으로 long타입 형변환을 한 후 sub_t라는 long 변수에 저장한다. long을 사용한 이유는 아래 오답노트에서 확인할 수 있다.

그리고 이렇게 구한 sub_t를 stol으로 long타입으로 형변환 한 p와 비교한다. sub_t가 작거나 같다면 answer을 1 늘려주어 업데이트 한다.

 

반복문이 끝나 t를 다 돌아보고 나면 answer에는 정답이 저장되어 있다.

 

 

오답 노트

sub_t와 p를 숫자로 변환할 때 long으로 변환하지 않아 오류가 발생하였다. int형의 데이터 크기는 4바이트(32비트)이며, 값의 범위는 -2,147, 483, 648~2,147,483,647이다. 따라서 제한 사항에 p의 길이가 18까지 길어질 수 있어 int는 모든 값을 담기에는 충분하지 않다. t도 마찬가지로 p보다 더 큰데다가 길이가 최대 10,000까지도 가니 int는 부족하다. 그래서 p와 t의 길이가 긴 테스트에서 오류가 몇개 발생하였는데 long과 stol을 사용하니 해결되었다.

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/147355

프로그래머스