글 읽기 - 시간초과

(追記) (追記ここまで)

시간초과

15565번 - 귀여운 라이언

suhee0206 5년 전 0

첫 번째 코드가 시간초과인 이유가 시간복잡도가 O(n^2) 이기 때문이라고 생각해서 코드를 아예 새로 짜서 시간복잡도를 O(n)으로 만드는 데 성공?했습니다. 그런데 또 시간초과가 뜨네요. 혹시 제 시간복잡도 계산이 틀린건가요... 어느 부분을 개선하면 시간초과가 안 날 지 알려주실 수 있나요????

/* 첫 번째 */
#include <iostream>
#include <vector>
using namespace std;
int N, k;
vector<int> info;
int num = 0;
int main() {
	ios::sync_with_stdio(false);
	cin >> N >> k;
	int doll;
	for (int i = 0; i < N; i++) {
		cin >> doll;
		info.push_back(doll);
	}
	int size = 0;
	int min = 0;
	for (int start = 0; start < N; start++) {
		if (info[start] == 1) {
			num++;
			int end = start + 1;
			while (num < k && end < N) {
				if (info[end] == 1) {
					num++;
				}
				end++;
			}
			if (num == k) {
				size = end - start;
				if (min != 0 && size < min) {
					min = size;
				}
				else if (min == 0) {
					min = size;
				}
			}
		}
		num = 0;
	}
	if (size == 0) {
		cout << -1;
	}
	else {
		cout << min;
	}
}
/* 수정 후 두 번째 */
#include <iostream>
#include <vector>
using namespace std;
int N, k;
vector<int> info;
int num = 0;
int main() {
	ios::sync_with_stdio(false);
	cin >> N >> k;
	int doll;
	for (int i = 0; i < N; i++) {
		cin >> doll;
		info.push_back(doll);
	}
	int size = 0;
	int min = 10000001;
	int start = 0, end = 0;
	while (end <= N) {
		if (num < k) {
			if (info[start] != 1) {
				start++;
				if (start > end) {
					end++;
				}
			}
			else if (info[end] == 1) {
				num++;
				end++;
			}
			else {
				end++;
			}
		}
		else if (num > k) {
			if (info[start] == 1) {
				num--;
			}
			start++;
		}
		else if (num == k) {
			size = end - start;
			if (min > size) {
				min = size;
				if (end == N) {
					break;
				}
			}
			if (end < N) {
				if (info[start] == 1) {
					num--;
				}
				start++;
			}
		}
	}
	if (size == 0) {
		cout << -1;
	}
	else {
		cout << min;
	}
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC