백준 34348 (C++) snupc 문자열 (Easy)

최초 업로드: 2025-09-24 03:52:16

최근 수정 시간: 2025-09-24 03:53:28

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] snupc 문자열 (Easy)

[문제 링크](https://www.acmicpc.net/problem/34348)

## 문제 설명

알파벳 <code>s</code>,<code>n</code>,<code>u</code>,<code>p</code>,<code>c</code>로만 이루어진 문자열 $S$가 주어진다.

$f(1)=$ <code>snupc</code>, $f(2)=$ <code>ssnnuuppcc</code>와 같이 $f(k)$를 <code>s</code>,<code>n</code>,<code>u</code>,<code>p</code>,<code>c</code> 각 $k$개가 순서대로 연속하여 이어진 문자열로 정의하자. $f(0)$은 빈 문자열을 의미한다.

$Q$개의 쿼리가 주어질 때, 다음을 처리하는 프로그램을 작성하라.

<ul>
	<li>$l$ $r$: $S$의 $l$번째 문자부터 $r$번째 문자까지를 이은 새로운 문자열에 대해, $f(k)$가 부분 수열(Subsequence)로 등장하도록 하는 $k$의 최댓값을 출력한다.</li>
</ul>

문자열의 부분 수열이란, 원래 문자열에서 $0$개 이상의 문자를 제거하여 얻을 수 있는 문자열을 말한다. 단, 남은 문자의 순서는 바꿀 수 없으며, 연속할 필요는 없다. 예를 들어 <code>abcde</code>의 부분 수열은 <code>ace</code>,<code>bd</code>,<code>a</code>,<code>abcde</code>, 빈 문자열 등이 해당한다.

## 입력

첫째 줄에 문자열 $S$가 주어진다. $(1 \le |S| \le 100\,000)$

둘째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \le Q \le 5\,000)$

셋째 줄부터 $Q$개의 줄에 걸쳐, 쿼리에 대한 정보 $l$, $r$이 공백으로 구분되어 주어진다. $(1 \le l \le r \le |S|)$

입력으로 주어지는 모든 수는 정수이다.

## 출력

각 쿼리에 대한 결과를 한 줄에 하나씩 출력한다.

## 풀이
각 쿼리마다 0 ~ length/5 사이에서 매개 변수 탐색을 하면서 문자열이 존재하는지 확인하며 최대 문자열의 길이를 구하면 됩니다.  
문자열이 존재하는지 빨리 확인하는 방법은 5개의 문자가 등장하는 위치들을 모아 놓고 s에서 이분 탐색, 그 위치부터 n에서 이분 탐색, 그 위치부터 u에서, 그 위치부터 p에서, 그 위치부터 c에서 이분 탐색 후에 그 위치가 입력된 범위를 벗어나지 않았는지 확인함으로써 알 수 있습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

string s;
string snupc = "snupc";
vector<vector<int>> arr(5);

bool chk(int l, int r, int cnt) {
 for(int i=0;i<5;i++) {
 l = lower_bound(arr[i].begin(), arr[i].end(), l)-arr[i].begin() + cnt-1;
 if(l>=arr[i].size() || arr[i][l]>r) return false;
 l = arr[i][l];
 }
 return true;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> s;
 for(int i=0;i<s.length();i++) arr[snupc.find(s[i])].push_back(i);

int q; cin >> q;
    while(q--) {
        int a, b; cin >> a >> b;

int left=0, right=s.length()/5;
 while(left<right) {
 int mid = (left+right+1)/2;
 if(chk(a-1, b-1, mid)) left=mid;
 else right=mid-1;
 }
 cout << left << '\n';
 }
}
```