백준 16472번. 고냥이(c++) / 투포인터

투포인터를 활용해 푸는 문제이다.

2020카카오인턴 기출 문제 3번인 보석쇼핑과 매우 유사한 문제이다.

유사 문제

https://programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

위 문제에 대한 코드도 블로그에 정리해 두었다.

https://jungahshin.tistory.com/10?category=830724

2020 카카오 인턴 코딩 테스트 - 3번. 보석쇼핑(c++)

 

내가 틀렸던 포인트는 2가지이다.

1) n이 문자열의 크기보다 클 경우, while문을 돌 필요 없이 그냥 문자열의 크기를 반환하면 된다.

2) while문을 돌면서 n>=num일 경우 End값을 증가시켰는데, 이 경우에는 End값이 문자열 끝에 왔을 때에 길이를 계산하지 못하고 while문을 탈출한다는 오류가 있었다. 따라서, End==s.size()-1일 경우 길이를 계산하도록 했다.

 

 

코드 첨부(c++)

// 고냥이
#include <iostream>
#include <map>
using namespace std;
 
int n;
string s;
map<char, int> kind;
int final = 0; // 최대 구간 길이
 
int main()
{
    cin>>n;
    cin>>s;
 
    int num = 0; // 종류
    int Start = 0;
    int End = 0;
 
    if(s.size()<=n){
        cout<<s.size()<<"\n";
    }else{
        while(Start<=End && End<s.size()){
            if(num<=n){ // End를 늘린다.
                if(Start<=End && End<s.size()){
                    if(kind.count(s[End])==0){
                        kind[s[End]] = 1;
                        num++;
                    }else{
                        kind[s[End]]++;
                    }
                    End++;
                    if(End==s.size()-1 && n>=num){
                        final = max(final, End-Start+1);
                    }
                }
            }else if(num>n){ // Start를 늘린다.
                if(Start<=End && End<s.size()){
                    kind[s[Start]]--;
                    if(kind[s[Start]]==0){
                        kind.erase(s[Start]);
                        num--;
                    }
                    Start++;
                }
            }
 
            if(num==n){
                // Start~End-1까지의 구간길이를 저장한다.
                final = max(final, End-Start);
            }
        }      
        cout<<final<<"\n";  
    }
 
    return 0;
}

 

문제 첨부

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

16472번: 고냥이