글 읽기 - 어떤걸 개선해야할지 잘모르겠습니다......

luckyquit 4년 전 0

for, while문이 너무 많이 돌고 있는 건 인지하였지만

저걸 무슨수로 개선해야할지 감이 안옵니다...

어림 잡아보니 전체루프 n번 그 안에 루프 m^3번 O(n*m^3) 이네요;

STL stack를 쓰지말고 배열을 stack처럼 사용할까요?

#include<stack>
#include<map>
#include<iostream>
#include<cstring>
using namespace std;
int main(void)
{
	ios::sync_with_stdio(false);

	const int sz = 100001;

	int n, m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		map<int,int> mapp;
		
		int teamCnt = 0;

		cin >> m;
		for (int j = 1; j <= m; j++)
			cin >> mapp[j];

		bool team[sz];
		memset(team, false, sizeof(team));
		for (int k = 1; k <= m; k++) {
			team[k - 1] = true;

			if (team[k])
				continue;

			bool visited[sz];
			memset(visited, false, sizeof(visited));

			stack<int> s;
			s.push(k);
			while (!s.empty()) {
				int src = s.top();
				int dest = mapp[src];

				visited[src] = true;
				s.pop();
				
				if (src == dest && s.size() == 0) {
					(teamCnt)++;
					team[src] = true;
					visited[src] = true;

					break;
				}
                
				if (k == mapp[src]) {
					s.push(src);
					while (!s.empty()) {
						int temp = s.top();
						team[temp] = true;
						s.pop();
						visited[temp] = true;
						(teamCnt)++;
					}
					break;
				}
                
				if (visited[dest])
					continue;
				if (visited[dest] || team[dest])
					continue;

				s.push(src);
				s.push(dest);
				visited[dest] = true;
			}

		}
		cout << m - teamCnt << endl;
	}
	return 0;
}

nahwasa 4년 전 0

일단 상당히 시간이 빠듯한 문제라, O(NM) (N:TC갯수 M:각 TC의 입력갯수)

이어야 통과 가능합니다.

STL를 쓰는것에 대한 문제는 아닙니다.

힌트로 예시는

2 3 4 5 6 7 8 9 10 9 3

라고 해봅시다.

이 경우 처음 1번부터 보면 1->2->3->4->5->6->7->8->9->10->9 입니다.

9와 10이 팀인걸 알 수 있죠?

이 경우 1번에서 타고 들어간것이지만 어쨌든 팀은 찾았고, 이제 다음으로 2번을 보는게 아니고

마지막을 바로 보면 됩니다. 11->3 끝.

M번으로 끝났죠.

luckyquit 4년 전 1

nahwasa 님 감사합니다.

시간복잡도를 O(NM)이라고 말씀하셨는데, 그렇게 결론 지으신 이유를 듣고 싶습니다!

제가 지금까지 문제를 보고 시간은 생각안하고 풀었어서 그런 결론은 어떤 것을 전제로 내리는 것인지 궁금합니다

nahwasa 4년 전 0

저도 늅늅이라.. 감히 이렇게 써도 될런지 모르겠네요. 일단 제 기준에서 씁니다.

보통 입력으로 주어지는 N을 보고 정합니다.

(TC갯수가 주어진다면 그것도 생각해야 하지만, 이 문제처럼 따로 TC갯수가 없다면 TC갯수는 생각 안해도 됩니다.
그 경우 무리 없을 만큼만 주어진다고 보심 됩니다.)

대략 기본 연산 1억번에 1초 잡구요. (실제론 더 되겠지만, O(~)로 따지니 실제론 좀더 많이 연산해야하니까요)

입력 N이 10만이라면, 기본적으로 O(N^2)이면 10억번으로 10초정도로 잡아야합니다.

그러니 입력갯수 10만개이상이면 아 이건 출제자가 O(N^2)이상으론 하지 말란거군! 이라고 생각하심 됩니다.
(물론 시간제한이 1,2초 이런 문제 기준으로요)

그러니 O(N)이나 O(NlogN)쪽으로 방향을 잡고 풀어야하는거죠.

O(NM)이라고 바로 말한 이유는 제가 풀었던 문제기 때문입니닼ㅋㅋㅋ

그리고 TC는 무시하고 O(M)이라고 하셔도 되구요.

luckyquit 4년 전 1

nahwasa 님 감사합니다

이해가 잘 안되서 그러는데 N이 10만이면 N^2은 100억인데 어째서 10억으로 잡으신거에요?

nahwasa 4년 전 0

그..그러게요.. 죄송합니다 ㅠ

0 갯수를 잘못셌..어요..

luckyquit 4년 전 1

nahwasa ㅎㅎㅎ아닙니다 감사합니다~

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

문제

문제

출처

ICPC

어떤걸 개선해야할지 잘모르겠습니다......

luckyquit 4년 전 0

nahwasa 4년 전 0

luckyquit 4년 전 1

nahwasa 님 감사합니다.

nahwasa 4년 전 0

luckyquit 4년 전 1

nahwasa 님 감사합니다

nahwasa 4년 전 0

luckyquit 4년 전 1

nahwasa ㅎㅎㅎ아닙니다 감사합니다~

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말