백준, BOJ, 16472번, 고냥이: C++ [CPP] ★★★★

투 포인터 좋은 예라고 볼 수 있다.

여기서 R의 예외조건에 대해서 알아야하는데

내가 짠 알고리즘에서는 R이 커져버려서 while문에 다시 못들어가는데 있었다.

 

 

 

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

---

 

#맞은 풀이

#include<bits/stdc++.h>

using namespace std;
 
int N;
string s;
map<char, int> kind;
int ans = 0; // 최대 구간 길이
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>N;
    cin>>s;
 
    int num = 0; // 종류
    int L = 0;
    int R = 0;
 
    if(s.size()<=N){
        cout<<s.size()<<"\n";
    }else{
        //R은 문자열보다 커져서는 안됨.
        //L은 R보다 작거나 같음
        while(L<=R && R<s.size()){
            
            //right 이동 조건
            if(num <= N){
                //지금 가리키는 right 원소가 
                //현재 map에 없으면
                //종류 추가
                if(kind.count(s[R]) == 0){
                    kind[s[R]] = 1;
                    num++;
                }else{
                    //종류가 같으면 개수 추가
                    kind[s[R]]++;
                }
                R++;
                                
                //위에서 R이 마지막 원소를 가리키게 된다면
                //R++연산 후에는 while문이 다시 돌 수 없다.
                //즉, 여기서 R++연산 후에 처리를 여기서 해주어야 한다.
                //그리고 만약 이 조건이 만족한다면
                //뒤에 조사해도 이것보다 작아지므로 조사할 필요 x
                if(R == s.size() - 1 && num <= N){
                    ans = max(ans, R-L+1);
                    break;
                }

            }
            //left 이동조건
            else{
                kind[s[L]]--;
                if(kind[s[L]] == 0){
                    num--;
                    kind.erase(s[L]);
                }
                
                L++;
            }
            //N개 이상이었는데 N개가 되었다면 해당 길이도 다시 업데이트
            
            if(num == N){
                ans = max(ans, R-L);
            }

        }      
        cout<<ans<<"\n";  
    }
 
    return 0;
}

 

다른 분의 풀이를 보면 예외없이 그냥 푼 경우도 있다.

#include <iostream>
#include <algorithm>
using namespace std;

const int N_MAX = 100000;

int n;
int letter[26];
char s[N_MAX + 1];

int main(){
    scanf("%d", &n);
    scanf("%s", s);
    
    int cnt = 1;
    int ans = 1;
    int left = 0;
    
    letter[s[0] - 'a'] += 1;
    
    
    
    //여기가 핵심인데
    //문자열의 길이만큼 반복한다. -> i는 증가 
    //내 경우 (R의 증가로 보면 된다)
    for (int i = 1; s[i] != 0; i++){
    
    	//i번째의 문자열에 대해서 업데이트한다.
        if (letter[s[i] - 'a'] == 0){
            cnt += 1;
        }
        letter[s[i] - 'a'] += 1;
        
        //만약 업데이트 후 종류가 N개가 넘었다면 왼쪽에서 제외시켜줘야한다.
        while(cnt > n){
            letter[s[left] - 'a'] -= 1;
            if (letter[s[left] - 'a'] == 0){
                cnt -= 1;
            }
            left += 1;
        }
        
        //즉, left 부터 i번째까지의 문자열 종류가 N개 이하가 되었다면
        //i는 문자열의 위치를 바로 가리키므로 +1해주어서 결괏값을 낸다.
        if (i - left + 1 > ans){
            ans = i - left + 1;
        }
    }
    printf("%d\n", ans);
    
    
    return 0;
}