BOJ 15565 - 귀여운 라이언

[jusung-c]

---

문제

https://www.acmicpc.net/problem/15565
난이도 : 실버 1

• 인형 총 N개
• (라이언 인형 K개 어피치 인형 N-K개 )
• (1 ≤ K ≤ N ≤100만)
• 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기

---

아이디어

연속 부분 수열에 관한 문제이므로 투 포인터 알고리즘으로 먼저 접근해보았다.

L과 R 포인터를 1로 설정한 후 R 포인터를 라이언 인형이 K개가 되도록 옮겨준 후 답을 갱신한다. 그 후 L 포인터를 옮겨준 후 위에 했던 R 포인트 옮기기 과정을 반복하면 된다.

---

이거 근데 for문 안에 while 문이라서 시간 복잡도가 O(N²)이 걸리는데 N의 최댓값이 10만이라서 최악의 경우 1초가 넘어갈 거라고 생각했는데 통과했다.

왜지..? 최악의 경우를 생각해보면 L과 R이 N까지 이동할텐데 그럼 분명 시간 초과가 나야하는데..

---

구현

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, K;
    static int[] nums;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        nums = new int[N + 1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() throws IOException {
        int R = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;

        for (int L = 1; L <= N; L++) {

            // L 포인터 옮기기 전 라이언 인형이었는지 체크
            if (nums[L-1] == 1) {
                sum--;
            }

            // R 포인터 옮기고 라이언 인형이면 sum++
            while (R + 1 <= N && sum < K) {
                R++;
                if (nums[R] == 1) {
                    sum++;
                }
            }

            // K개 이상일 경우 result 갱신
            if (sum == K) {
                result = Math.min(result, R - L + 1);
            }

        }

        // result 범위 체크 후 답 출력
        if (result > 0 && result <= N) {
            bw.write(result + " ");
        } else {
            bw.write(-1 + " ");
        }
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }
}

---

[ghdcksgml1]

이런식으로 덱으로도 풀 수 있어용

// 언어 : C++ , (성공/실패) : 1/1 , 메모리 : 5404 KB , 시간 : 60ms
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <string.h> // memset

using namespace std;

vector<int> v;
deque<int> dq;

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N,K; cin>>N>>K;
    for(int i=0;i<N;i++){
        int tmp;
        cin>>tmp;
        if(tmp==1){ // vector에 라이언의 좌표만 담기
            v.push_back(i);
        }
    }

    // 라이언이 K개 미만이라면 안되는 경우이므로 -1
    if(v.size() < K) {
        cout<<-1<<'\n';
        return 0;
    }
    
    // 덱에 초기값 넣기
    for(int i=0;i<K;i++){
        dq.push_back(v[i]);
    }

    int len = dq.back() - dq.front() + 1;

    // 라이언의 개수만큼 덱으로 앞에서빼고 뒤에서 넣기
    for(int i=K;i<v.size();i++){
        dq.pop_front(); // 앞에서 빼기
        dq.push_back(v[i]); // 뒤에서 넣기
        len = min(len, dq.back() - dq.front() + 1); // (맨뒤 라이언 좌표) - (맨앞 라이언 좌표) + 1
    }

    cout<<len<<'\n';

    return 0;
}