글 읽기 - 시간초과 문제 해결해주세요 ㅠㅠ

king3456 6년 전 0

답은 제대로 출력되는거 같은데(이 또한 맞는지는 모르겠네요!;;)

시간초과가 떠서 어떻게 줄여야 할지 모르겠네요... 생각엔 for문을 좀 줄여야 될거같은데 접근방법이 생각이 잘 안듭니다 ㅜㅜ

도와주세요!

#include <stdio.h>

char character[100000];
int left[100000];
int right[100000];
int razor[100000][2];
int pipe[100000][2];
int pipe_temp[10000];

int main(){
	int index = 0;			//문자열 총 인덱스
	int index_L = 0;		//문자열 왼쪽괄호 인덱스
	int index_R = 0;		//문자열 오른쪽괄호 인덱스
	int index_razor = 0;	//레이저 인덱스
	int index_pipe_start = 0;		//쇠막대기 인덱스
	int index_pipe_finish = 0;		//쇠막대기 인덱스
	int not_pipe;
	int fragment_num = 0;
	
	//(a) 문자 입력받기
	for (int i = 0; i < 100000; i++){
		scanf("%c", &character[i]);
		if (character[i] == '\n'){
			index = i;
			break;
		}
	}

	//(b) 문자열의 왼쪽괄호, 오른쪽괄호 분류하기
	for (int j = 0; j < 100000; j++){
		if (character[j] == '('){
			left[index_L] = j;
			index_L++;
		}
		else if (character[j] == ')'){
			right[index_R] = j;
			index_R++;
		}
		else
			break;
	}

	//(c) 레이저 분류하기
	for (int k = 0; k < index_L; k++){
		for (int m = 0; m < index_R; m++){
			if (left[k] + 1 == right[m]){
				razor[index_razor][0] = left[k];	//레이저 시작위치
				razor[index_razor][1] = right[m];	//레이저 끝위치
				index_razor++;
			}
		}
	}
	//(d)-(1) 쇠막대기 시작위치 정하기
	//조건 - left[]에 속하면서 razor[][0]에 속하지 않는다
	for (int n = 0; n < index_L; n++){
		not_pipe = 0;
		for (int t = 0; t < index_razor; t++){
			if (left[n] == razor[t][0]){
				not_pipe = 1;
			}
		}
		if (not_pipe == 0){
			pipe[index_pipe_start][0] = left[n];
			index_pipe_start++;
		}
	}
	//(d)-(2) 쇠막대기 끝위치 정하기
	//조건 - right[]에 속하면서 razor[][1]에 속하지 않는다
	for (int n = 0; n < index_R; n++){
		not_pipe = 0;
		for (int t = 0; t < index_razor; t++){
			if (right[n] == razor[t][1]){
				not_pipe = 1;
			}
		}
		if (not_pipe == 0){
			pipe_temp[index_pipe_finish] = right[n];
			index_pipe_finish++;
		}
	}
	for (int r = index_pipe_start - 1; r >= 0; r--){
		int start = pipe[r][0];
		for (int p = 0; p < index_pipe_finish; p++){
			if (start < pipe_temp[p]){
				pipe[r][1] = pipe_temp[p];
				pipe_temp[p] = -1;
				break;
			}
		}
	}
	//(e)잘라진 조각 개수 구하기
	//각 쇠막대기 마다 [조건] 만족하는 레이저 갯수 체크
	//각 쇠막대기 마다 (레이저 수+1) 조각 생성
	//[조건] - 쇠막대기 시작위치 < 레이저 시작위치 & 레이저 끝위치 < 파이프 끝위치

	for (int e = 0; e < index_pipe_start; e++){
		int start_pipe = pipe[e][0];
		int finish_pipe = pipe[e][1];
		int cnt = 0;
		for (int w = 0; w < index_razor; w++){
			if (start_pipe < razor[w][0] && razor[w][1] < finish_pipe){
				cnt++;
			}
		}
		fragment_num += cnt + 1;
	}

	printf("%d\n", fragment_num);

	return 0;
}

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

문제

문제

출처

ICPC

시간초과 문제 해결해주세요 ㅠㅠ

king3456 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말