글 읽기 - 시간 초과가 나는 이유를 모르겠습니다.

song98987 5년 전 0

입력 받은 n의 크기만큼 이차원배열을 동적할당으로 선언하고 문자열들을 입력 받아 삽입 정렬한 후에 문자열을 뒤집고 만약 순서상으로 앞에 있는 문자열보다 뒤에 있는 문자열의 사전상 순서가 더 빠르면 count++을 하도록 코드를 짰습니다.

cout, cin, endl 등이 문제인가 싶어 다 고치고 string도 문제가 되나 해서 string을 char 배열로 고쳐보기도 했지만 아직도 시간 초과가 뜨네요 ..

뭐가 문제일까요 ??

/*
	삽입정렬의 memset 오류
	cin, cout. endl 쓰지 말자!!!
*/
#include <iostream>
#include <string.h> // 이거 써줘야 strlen 등 이용 가능
//using namespace std;

int main() {
	char **s, **inverse_s;
	int n, count = 0; // initialize 해주기

	scanf("%d", &n);

	s = new char*[n];
	inverse_s = new char*[n];
	for (int i = 0; i < n; i++) {
		s[i] = new char[12];
		inverse_s[i] = new char[12];
	}

	for (int i = 0; i < n; i++) {
		getchar(); // 써주기
		scanf("%s", s[i]);
	}

	// 삽입 정렬
	char val[20];
	for (int i = 1, j; i < n; i++) {
		strcpy(val, s[i]);
		j = i - 1;
		while (j >= 0 && strcmp(s[j], val) > 0) {
			strcpy(s[j + 1], s[j]);
			j--;
		}
		strcpy(s[j + 1], val);
	}

	// inverse string
	for (int i = 0, len; i < n; i++) {
		len = 0;
		for (int j = 0; s[i][j]; j++) {
			len++;
		}
		for (int j = 0; s[i][j]; j++) {
			inverse_s[i][len-j-1] = s[i][j];
		}
		inverse_s[i][len] = NULL;
	}

	for (int i = 0; i < n-1; i++) {
		for (int j = i+1; j < n; j++) {
			if (strcmp(inverse_s[i], inverse_s[j]) > 0) {// s2가 s1 보다 사전 순으로 앞선다면. >0 넣어줘야!
				count++;
			}
		}
	}
	printf("%d", count);
}

sgchoi5 5년 전 0

N 값을 보면 최대 10 만입니다. 보통, N 값이 10 이 되면 시간복잡도는 NlogN 이 되어야 통과가 됩니다.

현재 코드는 이중 for 문이니 N² 으로 보이네요.

문제 힌트를 보시면 어떤 방법으로 풀어야 할지.. 감이 오실 듯 하고요.. 정 안되시면 CHCI 문제는 자료가 공개되어 있으니 참고하시길..

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

문제

문제

출처

ICPC

시간 초과가 나는 이유를 모르겠습니다.

song98987 5년 전 0

sgchoi5 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말