글 읽기 - 10610번 왜 시간 초과가 뜨는지 잘 모르겠습니다

dev_codingnam 6년 전 0

분명히 종만갓님께서 제한시간 1초면 보통 1억번의 연산을 잡으면 된다 하셨는데,

제 코드는 20만번+알파 정도의 연산만 수행하는데 자꾸 시간초과라고 알려주네요 ㅠㅠ

다른 사람들의 코드를 보아도, 원리는 저와 같아서 더더욱 모르겠네요.

코드 설명은 주석으로 하였습니다.

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
char arr[100001]; // 문자열을 입력받을 배열
int digit[10] = {0}; // 각각 숫자의 갯수를 배열에 저장하려 함. 1이 3개 있으면, digit[1] = 3;
int t; // 임시 변수
int ans = 0; //3의 배수인지 확인하기 위해 수들의 합을 더할 변수

// bool is_multiple_of_3(void){
// 	int total = 0;
// 	for(int i = 0; i < 10; ++i){
// 		total += (i%3)*digit[i];
// 		total = total%3;
// 	}

// 	if(total%3 == 0)
// 		return true;
// 	return false;
// }

int main(void){
	scanf("%s", arr); //문자열 입력 받음

	for(int i = 0; i < strlen(arr); ++i){ // 문자열 처리. 최대 10^5 연산 
		t = arr[i] - '0';
		digit[t]++;
		ans += t%3;
	}
    //이중 반복문이지만, 결국에는 문자가 10^5개만큼 있으므로 10^5 연산
	if(digit[0] != 0 && ans%3 == 0){ //0의 갯수 판정 및 3의 배수 판정
		for(int i = 9; i >= 0; --i){
			for(int j = 0; j < digit[i]; ++j){
				printf("%d", i);
			}
		}
		cout << endl;
	}else{
		cout << -1 << endl;
	}

	//결국에는 10^5 연산 2개 + 알파. 하지만 시간초과.

	return 0;
}

subinium 6년 전 1

strlen을 계속 연산해서 그런것 같습니다. 배열의 길이를 다른 변수에 저장하고 반복문을 돌려보세요!

dev_codingnam 6년 전 0

오 감사합니다! 해결되었어요!!

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

문제

문제

출처

ICPC

10610번 왜 시간 초과가 뜨는지 잘 모르겠습니다

dev_codingnam 6년 전 0

subinium 6년 전 1

dev_codingnam 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말