백준 16472 고냥이 c++ // 투포인터, 매개변수탐색, 투포의 핵심아이디어, set 존재여부 조사하는법

https://www.acmicpc.net/problem/16472

16472번: 고냥이

1. 시행착오

1. cnt에 e-1과 e를 비교하여 다르면 cnt를 1증가시킨다.

반례 : cac의 경우 실제 cnt는 2가 되어야하는데, 단순히 e와 e-1을 비교하면 ac에서 a!=c이므로 cnt가 증가되어 버린다..

2. 해결 : set에 현재 등장한 알파벳들을 저장한다 

 

2. 의사코드

1.while(str의 범위내인지 체크)

2. 현재 알파벳갯수가 n이하인경우 -> 너 가능성있어 -> e를 뒤로보내며 조사

거기에서 추가될녀석이 새로운놈이면 ss에도 추가

3. 위에서 추가했더니 n을 넘어감 -> 너 가능성없어 -> 접으셈 -> 현재s를 탐색대상에서 제외시킴(롤 접게만듬)

그리고 새로운 s로 처음부터 다시 반복.

 

3. 투포의 핵심아이디어

!!!가능성 없는 놈을 접게만든다(탐색범위에서 제외시킨다)!!!

이래야 입력이 숫자가 아닌 문자열, case, 등 고냥이 같은 문제에서도 확장이 가능하다!

 

4. set 존재여부 조사하는법

set.find(N)==set.end() //find함수는 N이 없으면 end() iter를 반환한다.

즉, find결과가 end()이면 N이 없는것이다!

 

4. 전체코드

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

typedef long long ll;

string str;
set<int> ss; //현재 알파벳 등장한것들 저장
int n, ret;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    cin >> str;

    int s = 0, e = 0;
    ss.insert(str[s]);


    while (s<str.size() && e<str.size()) {
        ret = max(ret, e - s + 1);

        if (ss.size() <= n) {
            e++;
            if (e < str.size() && ss.find(str[e]) == ss.end()) {
                ss.insert(str[e]);
            }
        }
        if (ss.size() > n) {
            s++;
            e = s;
            ss.clear();
            ss.insert(str[s]);
        }

    }

    cout << ret;

    return 0;
}

 

4. 파라매트릭 서치

이분탐색으로 풀수있는문제 -> 매개변수 탐색으로도 풀수있다

정답의 범위를 이분탐색하며, if(문제조건에 맞음) -> st=mid, en=mid로 할지 정하여 정답범위를 1/2로 줄이며 탐색하면된다.