[알고리즘 풀이 분석] BOJ 15565 귀여운 라이언

오늘 풀어본 문제는 BOJ 15565 귀여운 라이언 이다!
오늘 두 문제를 풀 생각이고 그 중에 첫번째 문제로 역시나 오늘의 문제 에서 골라 풀었다!
급하지 않게, 천천히 실수 없이 한번에 풀어서 맞추는게 목표였고 다행히 한번에 통과 됐다!

BOJ 15565 귀여운 라이언

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

입출력

나의 풀이

나열되어 있는 N 개 중에 연속된 K 개 이상의 라이언을 찾고 그 중 가장 짧은 거리 내에 있는 집합의 길이를 구하면 되는 문제이다.

K 개 이상의 라이언이라 하지만 최소 집합 크기를 구하는 문제이기 때문에 결국 첫번째 라이언 - K 번째 라이언 사이의 거리 중 가장 짧은 것을 구하면 된다.

두가지 변수를 사용하였다. 연속된 K 개의 라이언 중 가장 왼쪽에 있는 라이언의 위치를 담는 start 와 가장 오른쪽에 있는 라이언의 위치를 담을 end 이다. N개의 인형들을 한번에 쭉 탐색하면서 두 변수 start, end 를 변경 시키고 end-start+1 값 중 최솟값이 나오면 minSize 를 갱신하였다.

start 를 바꿔갈 때 지나온 라이언의 위치들을 알고 있어야 하므로 라이언을 만날 때 마다 배열 ryan 에 해당 위치를 추가시켜주며 기록하였다.

이렇게 풀고보니 이 문제가 투포인터 문제였다. 투포인터 알고리즘은 들어만 본 것 같아서 찾아보니까 그냥 이렇게 배열 내에서 두개의 포인터를 이용하는 방법이 투포인터 알고리즘이더라..!

코드

#include <iostream>
#include <vector>

// BOJ 15565 귀여운 라이언, 실버 1, 투포인터
using namespace std;

int getMinSize(vector<int> doll, int N, int K){
    bool exist = false;
    int minSize = 1000000;
    int start = -1, end = -1, j = -1;
    vector<int> ryan;

    for (int i = 0; i < N; ++i) {
        if (doll[i]==1){
            if (start == -1){  // 처음 등장한 라이언
                start = i;
                ryan.push_back(i);
                j = 0;
                continue;
            }

            if (ryan.size() < K-1 ){  // 두번째 ~ k-1 번째 등장한 라이언
                ryan.push_back(i);
                continue;
            }

            if (ryan.size() >= K){
                start = ryan[++j];
            }
            end = i;
            ryan.push_back(i);
            minSize = min(minSize, end-start+1);

            if(!exist) exist = true;
        }
    }

    if (!exist) return -1;
    else return minSize;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin>>N>>K;

    vector<int> doll(N, 0);
    for (int i = 0; i < N; ++i) {
        cin>>doll[i];
    }

    int answer = getMinSize(doll, N, K);
    cout<<answer;

    return 0;
}