C++로 주어진 파워 값을 갖는 부분 문자열 찾기

문제 설명

이 문제에서는 하나의 문자열 str과 정수 pow가 주어집니다. 우리의 목표는 주어진 파워(power) 값을 가지는 부분 문자열(substring)을 찾아 반환하는 것입니다.

여기서 문자열의 파워란 문자열을 구성하는 각 문자의 파워를 모두 더한 값입니다.

각 문자의 파워는 알파벳 순서 번호로 정의됩니다: a → 1, b → 2, c → 3, ...

예시로 문제 이해하기

입력 : string = "programming", power = 49
출력 : 'pro'

풀이 설명 −

"pro"의 파워 계산:
power(p) = 16
power(r) = 18
power(o) = 15
총합 = 16 + 18 + 15 = 49

해결 방법

1. 단순 접근: 중첩 루프 사용

가장 기본적인 해결 방법은 중첩 루프(nested loop)를 사용하는 것입니다. 외부 루프로 문자열을 순회하고, 내부 루프를 통해 가능한 모든 부분 문자열을 생성합니다. 각 부분 문자열의 파워를 계산한 뒤 pow와 일치하는지 확인하고, 일치하면 true를, 끝까지 찾지 못하면 false를 반환합니다. 이 방법은 직관적이지만 시간 복잡도가 O(n²)로 비효율적입니다.

2. 효율적인 접근: 해시 맵(Map) 활용

더 효율적인 방법은 해시 맵(unordered_map)을 이용해 누적 파워(접두사 합)를 저장하는 것입니다. 문자열을 한 번만 순회하면서 현재까지의 누적 파워(currPower)를 계산하고, 맵에 (currPower - pow) 값이 이미 존재하는지 확인합니다. 존재한다면 그 지점 다음부터 현재 위치까지의 부분 문자열이 정확히 pow의 파워를 가진다는 의미이므로 해당 부분 문자열을 출력하고 종료합니다. 문자열 전체를 순회했는데도 조건을 만족하는 값을 찾지 못하면 false를 반환합니다.

이 방식은 배열의 연속 부분 합 문제에서 널리 쓰이는 접두사 합(prefix sum) 기법을 응용한 것으로, 시간 복잡도를 O(n)까지 크게 줄일 수 있다는 장점이 있습니다.

알고리즘

1단계 − 문자열을 순회하며 현재까지의 누적 파워(currPower)를 계산합니다.
2단계 − (currPower - pow) 값이 맵에 존재하는지 확인합니다.
- 2.1단계 − 존재한다면, 해당 인덱스 다음 위치부터 현재 위치까지의 부분 문자열을 출력합니다.
3단계 − currPower 값을 맵에 삽입합니다.
4단계 − 문자열의 모든 문자를 순회했는데도 조건을 만족하는 부분 문자열을 찾지 못했다면, '찾을 수 없음'을 출력합니다.

구현 예제

아래 프로그램은 위 해결 방법의 실제 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
void findSubStringWithPower(string str, int power) {
   int i;
   unordered_map<int , int > powerSS;
   int currPower = 0;
   int N = str.length();
   for (i = 0; i < N; i++) {
      currPower = currPower + (str[i] - 'a' + 1);
      if (currPower == power) {
         cout<<"Substring : "<<str.substr((0), i+1)<<" has power "<<power;
         return;
      }
      if (powerSS.find(currPower - power) != powerSS.end()) {
         cout<<"Substring from index "<<str.substr((powerSS[currPower-power] + 1),(i - (powerSS[currPower - power] + 1)) + 1);
         cout<<" has power "<<power; return;
      }
      powerSS[currPower] = i;
   }
   cout<<"No substring found!";
}
int main() {
   string str = "programming";
   int power = 49;
   findSubStringWithPower(str, power);
   return 0;
}

출력 결과

Substring : pro has power 49

실행 결과, 문자열 "programming"에서 파워의 합이 49가 되는 부분 문자열 "pro"(p=16, r=18, o=15)를 성공적으로 찾아낸 것을 확인할 수 있습니다.