백준 16171번 [나는 친구가 적다 (Small)](C++) -yes6686- 티스토리

백준 문제 풀이: 16171 [나는 친구가 적다 (Small)]

---

문제 링크: https://www.acmicpc.net/problem/16171

문제 설명:

주어진 문자열 s에서 숫자를 모두 제거한 새로운 문자열을 생성한 뒤, 이 문자열에 특정 문자열 k가 포함되는지를 확인하는 문제입니다. 포함되면 1을, 포함되지 않으면 0을 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string s, k;
    cin >> s >> k; // 입력 문자열과 검색할 문자열

    string filtered = ""; // 숫자를 제거한 문자열 생성
    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i])) { // 알파벳만 추가
            filtered += s[i];
        }
    }

    // 필터링된 문자열에서 k 찾기
    if (filtered.find(k) != string::npos) {
        cout << 1; // k가 포함되어 있음
    } else {
        cout << 0; // k가 포함되지 않음
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 입력 문자열 s에서 숫자를 제거하고, 알파벳으로만 구성된 새로운 문자열 filtered를 만듭니다.
  • 문자열 filtered에 k가 포함되어 있는지 확인합니다.
• 구현 세부사항:
  • isalpha 함수: 현재 문자가 알파벳인지 확인합니다.
  • find 함수: filtered 문자열에서 k를 검색합니다. 검색에 성공하면 해당 위치를 반환하고, 실패하면 string::npos를 반환합니다.
• 시간 복잡도 분석:
  • 숫자 제거 과정: 문자열 s의 길이를 n이라 하면, O(n)입니다.
  • 문자열 검색: filtered의 길이를 m, k의 길이를 l라 하면, 검색의 복잡도는 O(m ⋅ l)입니다.
  • 전체 복잡도는 O(n + m ⋅ l)로, 문자열 크기가 작으므로 효율적입니다.

---

결과

입력 문자열에서 숫자를 제거한 뒤, 특정 문자열 k가 포함되는지를 정확히 판단합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!