글 읽기 - 정말 많이 고민해보았는데 시간초과가 해결되지 않네요. 조언 부탁드립니다!

kbear 5년 전 0

입력받은 배열을 직접 뒤집지도않고, 삭제 연산도 직접 삭제가 아니라 left, right 시작점을 가리키는 left_cursor, right_cursor 변수를 만들어서 O(1) 로 구현하였습니다.

질문 게시판에서 여러가지 질문을 확인하면서 제 코드의 문제점들을 해결하였고,

https://www.acmicpc.net/board/...

질문 답변에 많은 분들이 올려주신 이 게시물도 확인하고 제 코드에 반영하였습니다.

그런데도 시간 초과가 뜨네요 ㅠㅠ 이 문제에 매달린지 4일이 되어가는데 더이상 어느 부분이 잘못되었는지 저 스스로는 찾을 수 가 없을것 같아서 다른 분들의 조언이 필요합니다.

조언 부탁드립니다.

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

bool error_bit = false;
bool entrance = false; //false <-------arr------> true
int left_cursor, right_cursor;

int cnt_R(char p[], int start) {
	int size = strlen(p);
	int cnt = 0;
	for (int i = start; i < size; i++) {
		if (p[i] == 'R') cnt++;
		else break;
	}
	return cnt;
}
int cnt_D(char p[], int start) {
	int size = strlen(p);
	int cnt = 0;
	for (int i = start; i < size; i++) {
		if (p[i] == 'D') cnt++;
		else break;
	}
	return cnt;
}
void print_arr(int arr[]) {
	if (entrance) {
		for (int i = right_cursor; i > left_cursor; i--)
			cout << arr[i] << ",";
		cout << arr[left_cursor];
	}
	else {
		for (int i = left_cursor; i < right_cursor; i++)
			cout << arr[i] << ",";
		cout << arr[right_cursor];
	}
}
void D_func(int arr[], int n_of_D, int* arrSize) {
	if ((*arrSize) == 0) {
		error_bit = true;
		return;
	}
	int size = *arrSize;

	for (int i = 0; i < n_of_D; i++) {
		if ((*arrSize) == 0) {
			error_bit = true;
			return;
		}
		if (entrance == false) {
			left_cursor++;
			(*arrSize)--;
		}
		else {
			right_cursor--;
			(*arrSize)--;
		}
	}
}
int main() {
	cin.tie(NULL); cin.sync_with_stdio(false);
	int T; cin >> T;

	for (int i = 0; i < T; i++) {
		error_bit = false;
		entrance = false;
		char p[100001]; cin >> p;
		int n; cin >> n;
		int d = 0;
		
		int* arr = new int[400001];

		int index = 0;
		while (1) {
			char c = getchar();
			if (c >= '0' && c <= '9') d = d * 10 + c - '0';
			else {
				if (d > 0) arr[index++] = d;
				d = 0;
				if (c == ']') break;
			}
		}

		int arrSize = n;
		left_cursor = 0; right_cursor = n - 1;

		int p_len = strlen(p);
		int start = 0;
		while (1) {
			if(p_len == start) break;

			int n_of_R = cnt_R(p, start);
			start += n_of_R;
			if (n_of_R % 2 == 1) entrance = !(entrance);

			int n_of_D = cnt_D(p, start); 
			start += n_of_D;
			if (n_of_D == 0) continue;
			D_func(arr, n_of_D, &arrSize);
		}
		if (!(error_bit) && arrSize == 0) {
			cout << "[]\n";
			continue;
		}
		if (!(error_bit) && arrSize != 0) {
			cout << '[';
			print_arr(arr);
			cout << "]\n";
		}
		else if (error_bit)
			cout << "error\n";
	}
	return 0;
}

11, 20번째 줄에서 strlen(p)를 함수가 호출될 때마다 하고 있는데, 그러면 최악의 경우 하나의 케이스에서 strlen(p)를 무려 10만 번을 호출하게 됩니다. 매번 호출할 때마다 10만 개의 문자를 검사해야 하니까 100억이나 됩니다. 이는 해당 FAQ의 8번 "조건문 안에 strlen(str) 를 절대로 넣지 마세요. strlen은 문자열의 처음부터 널 문자가 나올 때까지 한 글자씩 확인하므로, 반복문을 한 바퀴 돌 때마다 문자열의 길이만큼의 시간이 걸립니다." 와 일맥상통하는 상황입니다.

kbear 5년 전 0

답글 정말 감사합니다!

이 문제가 정답률이 괜히 낮은게 아닌것 같아요.

조언해주신 부분 이해하고

strlen을 한번만 호출하는것도 시도해보고 아얘 호출하지 않는 방법도 생각해내서 시도해봤느데 시간초과가 또 떠버리네요

조언해주신 부분도 확실히 문제였고 추가적으로 다른데 문제가 또있는것같네요ㅠㅠ

조금 더 고민해봐야겠습니다.

감사합니다!

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

문제

문제

출처

ICPC

정말 많이 고민해보았는데 시간초과가 해결되지 않네요. 조언 부탁드립니다!

kbear 5년 전 0

djm03178 5년 전 1

kbear 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말