1. first 를 이용해 처음 구간부터 K 개가 발견된 상황까지의 원소개수를 구한다.
2. 마지막에 출력해준다.
import java.util.*; | |
import java.io.*; | |
/** | |
* https://www.acmicpc.net/problem/15565 | |
* BOJ 백준온라인져지 15565 귀여운 라이언 풀이 | |
*/ | |
public class Main { | |
public static void main (String args[]) throws IOException{ | |
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); | |
String str1[] = br.readLine().split(" "); | |
int N = Integer.parseInt(str1[0]); | |
int K = Integer.parseInt(str1[1]); | |
String str2[] = br.readLine().split(" "); | |
int min = Integer.MAX_VALUE; | |
int check = 0; | |
int tempResult = 0; | |
int first = -1; | |
for (int i = 0; i < N; i++) { | |
if (first >= 0) tempResult++; | |
if (str2[i].equals("1")) { | |
if (first == -1) { | |
first = i; | |
tempResult++; | |
} | |
check++; | |
if (check == K) { | |
if (min > tempResult) min = tempResult; | |
while (first < i) { | |
tempResult--; | |
first++; | |
if (str2[first].equals("1")) break; | |
} | |
check--; | |
} | |
} | |
} | |
bw.write(String.valueOf(min == Integer.MAX_VALUE ? -1 : min)); | |
bw.flush(); | |
} | |
} |
문제
꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.
입력
첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)
둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2)
출력
K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다.
'IT > 알고리즘' 카테고리의 다른 글
BOJ 백준온라인져지 1094 막대기 풀이 (0) | 2018.03.13 |
---|---|
BOJ 백준온라인져지 15562 네트워크 풀이 (0) | 2018.03.13 |
BOJ 백준온라인져지 2669 직사각형 네개의 합집합의 면적 구하기 풀이 (0) | 2018.03.10 |
BOJ 백준온라인져지 2668 숫자고르기 풀이 (0) | 2018.03.10 |
BOJ 백준온라인져지 2667 단지번호붙이기 풀이 (0) | 2018.03.09 |