프로그래머스 [연습문제 / 크기가 작은 부분 문자열](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 크기가 작은 부분문자열

---

문제 링크: 문제 보기

문제 설명:

문자열 t에서 길이가 p.size()인 부분 문자열들을 추출하여, 숫자로 변환한 후 p보다 작거나 같은 값의 개수를 찾는 문제입니다.

---

문제 해결 코드

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

int solution(string t, string p) {
    int answer = 0;
    int p_len = p.size();
    long long p_value = stoll(p); // 기준값을 정수로 변환

    for (int i = 0; i <= t.size() - p_len; i++) {
        string sub_str = t.substr(i, p_len); // 부분 문자열 추출
        long long sub_value = stoll(sub_str); // 정수 변환

        if (sub_value <= p_value) {
            answer++;
        }
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 문자열의 부분 문자열을 추출하고, 이를 정수로 변환한 후 비교하는 방식으로 해결합니다.
• 구현 세부사항:
• stoll 함수를 사용하여 문자열을 정수로 변환합니다.
• t.substr(i, p.size())를 이용해 길이 p.size()의 부분 문자열을 추출합니다.
• 각 부분 문자열을 변환한 후 p와 비교하여 작거나 같으면 카운트합니다.
• 시간 복잡도 분석:
• 부분 문자열 탐색: O(n)
• 각 부분 문자열을 정수로 변환: O(1)
• 총 시간 복잡도: O(n) (t의 길이에 비례)

---

결과

이 코드는 문자열의 부분 문자열을 추출하고, 이를 숫자로 변환하여 비교하는 방식으로 최적화되었습니다. 단순하면서도 효율적인 방법을 사용하여 문제를 해결합니다.

다른 접근 방식으로는 슬라이딩 윈도우 기법을 이용해 부분 문자열을 추출하는 방식도 있으며, 이는 특정 상황에서 실행 속도를 더 빠르게 만들 수 있습니다.