[Codeforces]Round #731. B

작성일 | In

B. Alphabetical Strings

문제 출처: https://codeforces.com/contest/1547/problem/B

  • 문제 요약

    “a” 부터 시작해서 양 끝 중 하나에 b, c, d, … 순으로 추가해서 만들 수 있는 string을 alphabetical string 이라고 한다.

    For example, the following strings are alphabetical: “a”, “ba”, “ab”, “bac” and “ihfcbadeg”. The following strings are not alphabetical: “z”, “aa”, “ca”, “acb”, “xyz” and “ddcba”.

    string이 주어질 때 그것이 alphabetical string 인지 아닌지 판별하라.

  • 문제 풀이

    문자열의 길이가 n일 때 문자열의 양 끝의 문자 중 최소한 하나는 a+(n-1)이어야 한다. 이 조건을 만족할 때 해당 문자를 제외한 문자열에서도 이 조건이 계속해서 만족한다면 alphabetical string이라고 할 수 있을 것이다.

  • 풀이 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define INF 1e9
#define ll long long
#define pii pair<int, int> 
#define foi(n) for(int i=0;i<n;++i)
#define endl '\n'
using namespace std;
 
int t;
string str;
void solve(){
    int len=str.length();
    char target;
    bool alpha=true;
    while(str.length()){
        target='a'+str.length()-1;
 
        if(str[str.length()-1]==target){
            str.pop_back();
        }
        else if(str[0]==target){
            str=str.substr(1, str.length()-1);
        }
        else{ //not alphabetical
            alpha=false;
            break;
        }
    }
    if(alpha) cout<<"YES\n";
    else cout<<"NO\n";
}
 
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    cin>>t;
    while(t--){
        cin>>str;
        solve();
    }
}