n개의 숫자로 이루어진 문자열 S가 있다고 가정해 보겠습니다. 정확히 11자리인 숫자는 첫 자리가 '8'로 시작할 때 전화번호로 간주됩니다. 우리는 한 번의 연산을 통해 S에서 임의의 숫자 하나를 제거할 수 있으며, 이 문자열을 유효한 전화번호로 만들 수 있는지 판별해야 합니다.
예를 들어 입력이 S = "5818005553985"라면 결과는 True(1)입니다. 앞쪽의 불필요한 숫자들을 제거하면 첫 글자가 '8'인 11자리 문자열 "8005553985"를 만들 수 있기 때문입니다.
문제 해결 접근 방법
이 문제는 다음과 같은 논리로 해결할 수 있습니다.
m := S의 크기 S의 끝에 '8' 삽입 만약 8의 위치 <= (m - 11)이면: true 반환 false 반환
동작 원리
여기서 핵심 아이디어는 두 가지입니다.
1. 센티널(Sentinel) 활용: 문자열 끝에 '8'을 하나 추가하면, 원래 문자열에 '8'이 없는 경우에도 find('8') 함수가 항상 유효한 위치를 반환하도록 보장할 수 있습니다.
2. 위치 조건 검사: 첫 번째 '8'의 위치를 i라고 할 때, 해당 위치부터 문자열 끝까지 남아 있는 숫자의 개수는 m - i개입니다. 유효한 전화번호는 정확히 11자리여야 하므로, i ≤ (m - 11)을 만족해야 합니다. 조건을 충족하면 그 '8'부터 시작해 나머지 숫자들을 제거하여 조건에 맞는 전화번호를 완성할 수 있습니다.
예제 코드
아래 C++ 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(string S){
int m = S.size();
S.push_back('8');
if ((int(S.find('8')) <= (m - 11)))
return true;
return false;
}
int main(){
string S = "5818005553985";
cout << solve(S) << endl;
}
입력
"5818005553985"
출력
1
출력값 1은 true를 의미하며, 주어진 문자열에서 유효한 전화번호를 만들 수 있음을 나타냅니다. 이 알고리즘은 문자열을 한 번만 탐색하면 되므로 시간 복잡도는 O(n)으로 매우 효율적입니다.