[Algorithm]Baekjoon 165번 :: 문자열 판별

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
 
int n, d, k, c;
int arr[3000001] = { 0 };
unordered_map<int, int> check;
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> d >> k >> c;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    for (int i = 0; i < k - 1; ++i)
    {
        ++check[arr[i]];
    }
 
    int start = 0;
    int end = k - 1;
    int answer = 0;
 
    for (int i = 0; i < n; ++i) // 반복용 for문
    {
        ++check[arr[end % n]];
 
        if (check.find(c) != check.end())
        {
            answer = max(answer, (int)check.size());
        }
        else
        {
            answer = max(answer, (int)check.size() + 1);
        }
 
        --check[arr[start]];
 
        if (check[arr[start]] == 0)
        {
            check.erase(check.find(arr[start]));
        }
 
        ++start;
        ++end;
    }
 
    cout << answer;
}
 
 

 

현재 k개의 연속된 초밥들이 뭐가 몇개들어있는지 map으로 관리하는건데, 통과는 하지만 시간이 좀 더 걸린다.

조금만 더 생각해보면 충분히 배열로도 체크할 수 있기 때문에 배열로도 풀어봤다.

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
 
int n, d, k, c;
int arr[3000001] = { 0 };
int check[3001] = { 0 };
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> d >> k >> c;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    int count = 1;
    ++check[c];
 
    for (int i = 0; i < k; ++i) // k개 먼저 체크.
    {
        if (check[arr[i]] == 0)
        {
            ++count;
        }
 
        ++check[arr[i]];
    }
 
    int answer = count;
 
    for (int i = 0; i < n; ++i)
    {
        if (check[arr[i]] - 1 == 0)
        {
            --count;
        }
 
        --check[arr[i]];
 
        if (check[arr[(i + k) % n]] == 0) // 현재 연속목록에 없는 초밥을 추가하는경우
        {
            ++count;
        }
 
        ++check[arr[(i + k) % n]];
 
        answer = max(answer, count);
    }
 
    cout << answer;
}
 
 

 

 

여기서 포인트는 미리 추가주문초밥을 카운팅하는것. (check랑 count 둘 다)

어차피 반드시 추가로 먹을 수 있기 때문이다.

 

이런유형 간만에 풀어서 그런지 이쪽으로 머리가 잘 안돌아갔다.. 막 엄청 쉬운 문제는 아니였지만, 그래도 빠릿빠릿하게 풀어야할텐데