[백준 16171] 나는 친구가 적다 (Small) (C#, C++) - soo:bak

문제 링크

16171번 - 나는 친구가 적다 (Small)

설명

교과서 문자열 S와 키워드 K가 주어지는 상황에서, S의 길이 (1 ≤ S ≤ 100), K의 길이 (1 ≤ K ≤ 100)가 주어질 때, S에서 숫자를 모두 제거한 후 K가 부분 문자열로 존재하는지 확인하는 문제입니다.

교과서 문자열 S는 알파벳 대소문자와 숫자(0-9)로 이루어져 있습니다. 키워드 K는 알파벳 대소문자로만 이루어져 있습니다. S에서 숫자를 모두 제거한 후, 남은 문자열에 K가 연속된 부분 문자열로 존재하면 1을, 아니면 0을 출력합니다.

접근법

S에서 숫자를 제거한 새로운 문자열을 만든 후, K가 부분 문자열로 존재하는지 확인합니다.

S를 처음부터 끝까지 순회하면서 숫자가 아닌 문자(알파벳)만 새로운 문자열에 추가합니다. StringBuilder나 문자열 변수를 사용하여 필터링된 문자열을 만듭니다.

필터링이 완료된 문자열에서 K를 검색합니다. 문자열 검색 함수(Contains, find)를 사용하면 K가 부분 문자열로 존재하는지 확인할 수 있습니다. K가 발견되면 1을, 발견되지 않으면 0을 출력합니다.

예를 들어, S = “a1b2c3def”이고 K = “bcd”인 경우:

S에서 숫자를 제거하면 “abcdef”가 됩니다. 이 문자열에서 “bcd”를 찾으면 인덱스 1에서 발견되므로 1을 출력합니다.

반면 S = “a1b2c3def”이고 K = “xyz”인 경우, 숫자를 제거한 “abcdef”에 “xyz”가 없으므로 0을 출력합니다.

문자열 길이가 최대 100이므로 필터링은 O(|S|), 검색은 O(|S| × |K|)입니다. 전체 시간 복잡도는 O(|S| × |K|)이며, 주어진 제약에서 충분히 빠릅니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      string s = Console.ReadLine()!;
      string k = Console.ReadLine()!;

      StringBuilder filtered = new StringBuilder();
      foreach (char ch in s) {
        if (!char.IsDigit(ch)) filtered.Append(ch);
      }

      string result = filtered.ToString();
      Console.WriteLine(result.Contains(k) ? 1 : 0);
    }
  }
}

C++

#include <bits/stdc++.h>

using namespace std;

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

  string s, k; cin >> s >> k;
  string filtered;
  filtered.reserve(s.size());
  for (char ch : s) {
    if (!isdigit(static_cast<unsigned char>(ch)))
      filtered.push_back(ch);
  }

  if (filtered.find(k) == string::npos) cout << 0 << "\n";
  else cout << 1 << "\n";

  return 0;
}