글 읽기 - [c++] 시간복잡도 관련 질문드립니다.

sue5750 4년 전 0

일단 채점 결과는 맞았다고 나왔는데 제출 전에 37~46번째 줄 부분이 시간초과가 뜨지 않을까 생각했습니다.

저 부분의 시간복잡도를 어떻게 계산하면 좋을지 답변 부탁드립니다.

또한 혹시 코드를 개선시킬 수 있다면 개선시킬 수 있는 방법이 어떤게 있을까요?

답변 감사드립니다!

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstring>
#include <utility>
#include <vector>

using namespace std;

int main() {

	char p_list[100003];
	scanf("%s", p_list);

	int p_length = strlen(p_list);

	vector<pair<char, int>> D;
	vector<pair<int, int>> L; // 레이저의 위치를 저장
	vector<pair<int, int>> S; // 막대기의 위치를 저장
	D.push_back(make_pair(p_list[0], 0));
	// 시간 복잡도: O(100000)
	for (int i = 0; i < p_length; i++) {
		if (D.back().first == '(' && p_list[i] == ')') {
			if (D.back().second + 1 == i) {
				L.push_back(make_pair(D.back().second, i));
				D.pop_back();
			}
			else {
				S.push_back(make_pair(D.back().second, i));
				D.pop_back();
			}
		}
		else {
			D.push_back(make_pair(p_list[i], i));
		}
	}

	// 시간 복잡도: 
	// 조각의 총 개수 = 원래 막대기의 수 + 잘린 횟수의 총 합
	int result = S.size();
	for (int i = 0; i < S.size(); i++) {
		for (int j = 0; j < L.size(); j++) {
			if (S[i].first <= L[j].first && S[i].second >= L[j].second) {
				result++;
			}
		}
	}

	printf("%d", result);

	return 0;
}

ha_ram 4년 전 0

위의 코드를 보면 모든 막대의 위치와 레이저의 위치를 계산하신다음 막대마다 레이저로 잘리는지 아닌지를 판별하신것 같은데

잘 하셨는데 그렇게하시면 시간이 오래걸립니다.

이 문제의 알고리즘 분류가 스택으로 되어있는 이유는 스택을 이용하면 빠르고 간단하게 풀 수 있기 때문입니다.

스택을 이용하여 어떻게 풀 수 있을지 생각해보시구 그래도 잘 모르시겠다면 다시 질문해주시기 바랍니다.

sue5750 4년 전 1

@ha_ram 답변 감사합니다😊 더 고민해보고 모르겠으면 질문 드리겠습니다

djm03178 4년 전 0

참고로 시간 복잡도상 O((길이)^2)이기는 한데, 상수가 1/16 정도밖에 안 돼서 최악의 데이터를 넣어도 1초 내에는 충분히 통과합니다. 2만 5천 쌍씩을 S와 L에 각각 넣을 때 루프를 도는 횟수가 최대가 되는데 그래도 6억 2천 5백만밖에 안 되고 루프 내용물도 단순한 편이라서 오래 걸리게 만들 수가 없습니다.

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

문제

문제

출처

ICPC

[c++] 시간복잡도 관련 질문드립니다.

sue5750 4년 전 0

ha_ram 4년 전 0

sue5750 4년 전 1

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말