[15565] 귀여운 라이언(C++)

문제

바로가기

꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.

 

 

입력

첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)

둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2)

 

 

출력

K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다.

 

 

알고리즘

• 투포인터
• 슬라이딩 윈도우

 

 

해결 방법

인형의 개수가 최대 1000000이기 때문에 브루트포스로 인덱스가 0~1, 0~2, 0~3, 1~2, 1~3.... 사이일 때의 라이언의 개수를 일일이  찾으려고 한다면 1000000C2로 시간 초과가 난다.

따라서 라이언의 위치만을 가지고 크기가 K인 슬라이딩 윈도우로 문제를 풀면 된다.

문제의 예시에서 라이언의 위치는 [0, 4, 6, 9]이고 K = 3이므로 1000000, (6 - 0 + 1), (9 - 4 + 1) 중에 최솟값을 찾으면 되고, 답은 6이 된다.

 

 

내 코드

// [15565] 귀여운 라이언
// 투포인터, 슬라이딩 윈도우
#include <iostream>
#include <vector>
#define MAX 1000001
using namespace std;

int n, k;
vector<int> rionPos;

void input()
{
    int doll;
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> doll;
        if(doll == 1) rionPos.push_back(i);
    }
}

void solve()
{
    int ans = MAX;
    if(rionPos.size() < k) {
        cout << "-1\n";
    }
    else {
        for(int i = 0; i <= rionPos.size() - k; i++) {
            ans = min(ans, rionPos[i+k-1] - rionPos[i] + 1);
        }
        cout << ans << '\n';
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    solve();

    return 0;
}