글 읽기 - 시간초과가 발생합니다.

legendmic2 2년 전 0

처음엔 vector를 3개정도 사용했는데 시간초과가 떠서 벡터를 전부 지웠습니다.

그래도 시간초과가 뜨네요...ㅠㅠ 어떤부분이 문제인지 궁금합니다... string을 사용하면 안되는걸까요?

더 간단하게 푸는 방법이 있던데, 이 방법으로는 시간내에 못푸는걸까요?

읽어주셔서 감사합니다!

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	string str;
	stack<int> Loc; // 여는 괄호가 들어간 위치를 저장
	cin >> str;
	int stickStt[50000] = {};
	int stickEnd[50000] = {};
	int stickCnt = 0;
	double laserLoca[50000] = {};
	int laserCnt = 0;
	// vector<double> laserLoc; // 괄호의 위치를 0 이상의 정수라고 한다면 레이저는 x.5꼴로 저장
	bool isParOpened = false; // 직전에 괄호가 열렸었는가 -> 레이저를 확인하기 위함
	// Parentheses
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			Loc.push(i);
			isParOpened = true;
		}
		else {
			if (isParOpened) {
				laserLoca[laserCnt++] = i - 0.5; // 괄호가 6, 7에서 열리고 닫혔다면 레이저 위치는 6.5
				Loc.pop();
				isParOpened = false;
			}
			else {
				stickStt[stickCnt] = Loc.top();
				stickEnd[stickCnt++] = i;
				// Loc.top엔 가장 마지막으로 나타난 열린 괄호의 위치가 저장
				// 쇠막대기는 그곳부터 현재 닫힌 괄호의 위치(=i)까지의 길이를 가질 것
				Loc.pop();
			}
		}
	} // 쇠막대기 위치, 레이저 위치 저장 완료

	int stickPieces[50000] = {};
	for (int i = 0; i < stickCnt; i++)
	{
		stickPieces[i] = 1; // 레이저로 잘려지기 전의 막대기는 1개이므로 모두 1로 초기화
	}

	for (int i = 0; i < stickCnt; i++)
	{
		int cnt = 0;
		while (cnt != laserCnt) {
			if (stickStt[i] < laserLoca[cnt] && laserLoca[cnt] < stickEnd[i]) {
				// 막대의 시점과 종점 사이에 레이저가 있다면
				// 레이저의 위치는 실수, 쇠막대기의 시점/종점은 정수이므로 같을때의 경우는 고려X
				stickPieces[i]++; // 레이저로 한번 잘려진 i번째 쇠막대기의 총 파편수는 1 증가
			}
			cnt++;
		}
	}
	int sum = 0;
	for (int i = 0; i < stickCnt; i++)
	{
		sum += stickPieces[i];
	}
	cout << sum;
}

djm03178 2년 전 2

매우 간단하게 푸는 방법이 있습니다, 알고리즘 분류를 보세요.

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

문제

문제

출처

ICPC

시간초과가 발생합니다.

legendmic2 2년 전 0

djm03178 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말