글 읽기 - 어디서 시간초과가 났을까요? ㅜㅠ 도와주세요~!

wonmo 7년 전 0

visit는 현재 탐색에서 탐색했는지를 저장하는 배열이고

check는 모든 탐색에서 탐색했는지를 저장합니다.

탐색은 현재 탐색하는 인덱스가 check가 탐색되었는지까지 탐색합니다.

이 때 check된 인댁스가 현재 탐색에서 탐색되었다면 사이클이 생기는 거므로 그만큼을 check로 끊긴 인덱스를

저장하고 뒤돌아 가면서 이 인덱스를 만날때 까지 스택에서 팝하며 이 값만큼

전체 m에서 1씩 제거 합니다.

어디에서 잘못되었을까요..? ㅠ

#include<iostream>
#include<stack>
#include<cstring>
#include<deque>
using namespace std;
int arr[100100];
bool visit[100100];
bool check[100100];

int main() {
	int k;
	scanf("%d", &k);
	while (k--) {
		int m;
		memset(check, 0, 100100);
		stack<int> st;
		scanf("%d", &m);
		int countNum = m;
		for (int i = 1;i <= m;i++) {
			scanf("%d", &arr[i]);
		}
		for (int i = 1;i <= m;i++) {
			if (!check[i]) {
				memset(visit, 0, 100100);
				st.push(i);
				int temp = st.top();
				visit[temp] = true;
				while (!check[arr[temp]]) {
					check[temp] = true;
					visit[arr[temp]] = true;
					st.push(arr[temp]);
					temp = st.top();
				}
				int cycle = arr[temp];
				if (visit[cycle]) {
					do {
						countNum--;
						temp = st.top();
						check[temp] = true;
						st.pop();
					} while (temp != cycle);
				}
				while (!st.empty()) {
					st.pop();
				}
			}
		}
		printf("%d\n", countNum);
	}

	return 0;
}

wonmo 7년 전 0

24행에 있던 memset함수때문에 시간 초과 걸렸었습니다. 바보같이 memset의 시간복잡도를 고려 안 했었어요

저부분을 제외하고 스택에서 팝할때마다 해당 변수의 visit를 false로 만들어서 AC받았습니다.

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

문제

문제

출처

ICPC

어디서 시간초과가 났을까요? ㅜㅠ 도와주세요~!

wonmo 7년 전 0

wonmo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말