Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 목표 문자열을 만들기 위한 최소 부분 수열 개수 구하기

문제 소개

문자열이 하나 주어졌을 때, 몇 개의 문자를 삭제하거나 아무것도 삭제하지 않은 상태로 그 문자열의 부분 수열(subsequence)을 만들 수 있습니다. 이제 두 문자열 source와 target이 주어진다고 가정해 봅시다. 우리가 구해야 하는 것은 source의 부분 수열들을 이어 붙였을 때 target과 완전히 같아지도록 하는 부분 수열의 최소 개수입니다. 만약 어떤 방법으로도 불가능하다면 -1을 반환합니다.

예를 들어 source = "abc", target = "abcbc"인 경우를 살펴보겠습니다. "abc"와 "bc" 두 개의 부분 수열을 이어 붙이면 "abcbc"가 되므로, 정답은 2입니다.

접근 방법

이 문제를 효율적으로 해결하기 위해 다음 단계를 따릅니다.

1단계: 가능 여부 검사 함수 정의

  • s와 t를 입력으로 받는 possible 함수를 정의합니다.
  • 맵(map) m을 생성합니다.
  • s의 각 문자 c에 대해 m[c] = 1로 표시합니다.
  • t의 각 문자 c에 대해 m[c]가 0이면 false를 반환합니다. 즉, t에 s에 없는 문자가 포함되어 있으면 답을 만들 수 없습니다.
  • 모든 검사를 통과하면 true를 반환합니다.

2단계: 이진 탐색으로 최소 개수 계산

  • ssz는 s의 길이, tsz는 t의 길이로 설정합니다.
  • 키는 문자 타입, 값은 인덱스 배열(vector) 타입인 맵 m을 생성합니다.
  • i를 0부터 ssz - 1까지 반복하면서 m[s[i]]에 인덱스 i를 삽입합니다. 이렇게 하면 각 문자가 s에서 등장하는 모든 위치를 저장할 수 있습니다.
  • pre = -1, ret = 1로 초기화합니다. pre는 마지막으로 사용한 위치를 의미하고, ret은 필요한 부분 수열의 개수입니다.
  • i를 0부터 tsz - 1까지 반복합니다.
    • t[i]가 맵 m에 존재하지 않으면 -1을 반환합니다.
    • v = m[t[i]]로 해당 문자의 위치 배열을 가져옵니다.
    • upper_bound(이진 탐색)를 사용해 v에서 pre보다 큰 첫 번째 원소의 위치를 찾습니다.
    • 그런 원소가 없다면(it == v.end()) 현재 부분 수열로는 더 이상 진행할 수 없으므로 ret을 1 증가시키고, pre = v[0]으로 되돌려 새로운 부분 수열을 시작합니다.
    • 원소가 있다면 pre = *it로 갱신하여 같은 부분 수열 내에서 계속 진행합니다.
  • 반복이 끝나면 ret을 반환합니다.

핵심 아이디어는 각 문자의 등장 위치를 미리 저장해 두고, upper_bound를 통한 이진 탐색으로 다음 매칭 위치를 빠르게 찾는 것입니다. 덕분에 전체 시간 복잡도는 O(|t| × log|s|)로 효율적입니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool possible(string s, string t){
      map <char, int> m;
      for(int i = 0; i < s.size(); i++){
         m[s[i]] = 1;
      }
      for(int i = 0; i < t.size(); i++){
         if(!m[t[i]])return false;
      }
      return true;
   }
   int shortestWay(string s, string t) {
      int ssz = s.size();
      int tsz = t.size();
      map <char, vector <int> > m;
      for(int i = 0; i < ssz; i++){
         m[s[i]].push_back(i);
      }
      int pre = -1;
      int ret = 1;
      for(int i = 0; i < tsz; i++){
         if(!m.count(t[i]))return -1;
         vector <int>& v = m[t[i]];
         vector <int> :: iterator it = upper_bound(v.begin(),
         v.end(), pre);
         if(it == v.end()){
            ret++;
            pre = v[0];
         }else{
            pre = *it;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestWay("abc", "abcbc"));
}

입력

"abc"
"abcbc"

출력

2

정리

이 문제는 그리디(greedy) 기법과 이진 탐색을 결합한 대표적인 문자열 처리 문제입니다. source의 각 문자별 등장 위치를 맵에 저장해 두면, target을 순회하면서 현재 부분 수열에서 매칭 가능한 다음 위치를 upper_bound로 빠르게 찾을 수 있습니다. 매칭이 불가능해지는 순간 새로운 부분 수열을 시작하는 방식으로, 최소 개수를 정확하게 계산할 수 있습니다.