🌱문제 설명
꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.
입력
첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)
둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2)
출력
K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다.
풀이
#include <iostream>
#include <algorithm>
#include <climits> // INT_MAX 상수를 사용하기 위한 헤더 파일 추가
using namespace std;
int main() {
int N, K;
cin >> N >> K;
int arr[N];
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int left = 0;
int right = 0;
int count = 0;
int minSize = INT_MAX; // 최소 부분배열의 길이
while (right <= N-1) {
while (count < K && right <= N-1) { // count가 K 미만이거나 right가 N-1 이하인 경우에만 반복
if (arr[right] == 1) {
count++;
}
right++;
}
while (count == K) { // count가 K인 경우에만 반복
minSize = min(minSize, right - left); // 최소 부분배열의 길이 갱신
if (arr[left] == 1) {
count--;
}
left++;
}
}
if (minSize == INT_MAX) {
cout << -1;
} else {
cout << minSize;
}
return 0;
}❣️문제 요약:
라이언을 1로 어피치를 2로해서 연속해서 입력받는다. 나열된 순서를 바꾸지 않고 라이언이 k만큼 포함되는 가장 작은 배열을 찾는다.
🤔 생각해야 할 점
-
1,2의 순서를 바꾸면 안된다.
-
1,2의 순서는 N개 만큼 배열로 입력
-
가장 작은 수의 인덱스가 들어가면서 1이 k개 포함되는 배열을 찾기
-> 문제 조건 : 투 포인터로 배열 검사
→ 투 포인터로 left, right인덱스를 첫 인덱스로 초기화해서 right가 라이언이면 count를 증가시키고 left가 라이언이면 포인터를 옮기고 count를 감소한다.
- 코드 설명
✅ 인형 총 개수, 최소로 있어야할 라이언 수 , 인형 배열 입력
int N, K;
cin >> N >> K;//N인형수, K 최소 라이언 수
int arr[N];//인형 배열
for (int i = 0; i < N; i++) { // 라이언과 어피치 입력
cin >> arr[i];
}
✅ 투 포인터 left와 right를 맨 앞 인덱스로 초기화
int left = 0;//포인터 위치 인덱스 0번으로 설정
int right = 0;
int count = 0;//라이언의 수 세기
int minSize = INT_MAX; // 최소 부분배열의 길이(가장 큰 정수로)✅ 포인터 오른쪽이 배열을 벗어나지 않는 범위에서 오른쪽 포인터가 가르키는 인덱스가 라이언이면 라이언 수를 늘리고 인덱스를 옮겨준다. 왼쪽 포인터가 가르키는 인덱스가 라이언이면 오른쪽 포인터와 라이언 수가 중복되니까 빼주고 왼쪽포인터를 한 칸 이동시킨다.
✅ 라이언 수를 count에 저장해서 K가 만족되면 배열의 크기를 minSize에 저장해서 매번 더 작은 배열 크기로 갱신해준다.
while (right <= N-1) {
while (count < K && right <= N-1) { // count가 K 미만이거나 right가 N-1 이하인 경우에만 반복
if (arr[right] == 1) {
count++;
}
right++;
}
while (count == K) { // count가 K인 경우에만 반복
minSize = min(minSize, right - left); // 최소 부분배열의 길이 갱신
if (arr[left] == 1) {
count--;
}
left++;
}
}
✅ 배열의 크기가 갱신되지 않은 경우 ( 라이언이 K갯수만큼 없는 경우 -1 )
배열이 갱신 된 경우 가장 작은 인형 수의 배열 minSize 출력
if (minSize == INT_MAX) {
cout << -1;
} else {
cout << minSize;
}
🔥 어려웠던 점
- 처음에 작성한 코드
#include <iostream>
#include <algorithm>
#include <climits>
// INT_MAX 상수를 사용하기 위한 헤더 파일 추가
using namespace std;
int main() {
int N, K;
cin >> N >> K;//N인형수, K 최소 라이언 수
int arr[N];//인형 배열
for (int i = 0; i < N; i++) { // 라이언과 어피치 입력
cin >> arr[i];
}
int left = 0;//포인터 위치 인덱스 0번으로 설정
int right = 0;
int count = 0;//라이언의 수 세기
int minSize = INT_MAX; // 최소 부분배열의 길이(가장 큰 정수로)
while (right <= N-1) {
while(count <= K){
if (arr[right] == 1) {
count++;
}
right++;
else {
if (arr[left] == 1) {
count--;
}
left++;
}
}
if (count == K) {
minSize = min(minSize, right - left +1);
}
}
if (minSize == INT_MAX) {
cout << -1;
} else {
cout << minSize;
}
return 0;
}- 코드 설명
✅ 인형 총 개수, 최소로 있어야할 라이언 수 , 인형 배열 입력
int N, K;
cin >> N >> K;//N인형수, K 최소 라이언 수
int arr[N];//인형 배열
for (int i = 0; i < N; i++) { // 라이언과 어피치 입력
cin >> arr[i];
}
✅ 투 포인터 left와 right를 맨 앞 인덱스로 초기화
int left = 0;//포인터 위치 인덱스 0번으로 설정
int right = 0;
int count = 0;//라이언의 수 세기
int minSize = INT_MAX; // 최소 부분배열의 길이(가장 큰 정수로)✅ 포인터 오른쪽이 배열을 벗어나지 않는 범위에서 오른쪽 포인터가 가르키는 인덱스가 라이언이면 라이언 수를 늘리고 인덱스를 옮겨준다. 왼쪽 포인터가 가르키는 인덱스가 라이언이면 오른쪽 포인터와 라이언 수가 중복되니까 빼주고 왼쪽포인터를 한 칸 이동시킨다.
✅ 라이언 수를 count에 저장해서 K가 만족되면 배열의 크기를 minSize에 저장해서 매번 더 작은 배열 크기로 갱신해준다.
while (right <= N-1) {
while(count <= K){
if (arr[right] == 1) {
count++;
}
right++;
else {
if (arr[left] == 1) {
count--;
}
left++;
}
}
if (count == K) {
minSize = min(minSize, right - left +1);
}
}‼️ right , left 의 while문 조건을 다르게 설정해야했던 것 같다. 코드 길어질까봐 통일했더니 그래서 계속 런타임 에러 난듯
