제c++ 코드에서 어디가 최적화 가능할가요?

https://www.acmicpc.net/problem/2119
혹시 몰라서 위에는 지금 풀고 있는 문제

예제 입력은 되는데 검사해보면 계속 최적화 한다고 해도 시간 초과라고 떠서 질문드려 봅니다.
아래 코드에서 어디 부분을 고쳐야 빨라질까요?

클래스 선언 및 정의 부분 & 나머지

#include <iostream>
#include <vector>
#include <string>

/*
vector안에 모든 명령어 넣어놓고 차례로 실행하는 형식
*/


//사용가능한 명령들
enum {
	IFGO, JUMP, PASS, LOOP, DIE
};

class order {
public :
	virtual void DoThisWork(const std::vector<order*> &command, unsigned long int& printcount, int& idx) const = 0;
};


class Ifgo :public order {
private :
	int m1;

public :
	Ifgo(int m1) :m1(m1) {};
	//m1번줄로 이동 (idx = m1), 출력횟수가 최대가 되게해야하기 때문에 참인지 거짓인지 검사는 생략
	virtual void DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx) const;
};


class Jump :public order {
private :
	int m1;

public :
	Jump(int m1) :m1(m1) {};
	//m1번째 줄로 이동(idx = m1)
	virtual void DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const;
};


class Loop :public order {
private :
	int m1;
	int m2;

public :
	Loop(int m1, int m2) :m1(m1), m2(m2) {}

	//m1째 줄 부터 loop명령어 있는 부분까지 m2-1번 반복
	virtual void DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const;
};


class Pass :public order {
public :
	//다음줄로 넘어감 (idx++)
	virtual void DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const;
};


class Die :public order {
public:
	//프로그램 종료
	virtual void DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const;
};


void Ifgo::DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const {
	printcount++;

	idx = m1;

	return;
}

void Jump::DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const {
	printcount++;

	idx = m1;

	return;
}

void Loop::DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const {
	printcount++;

	int idx_ = m1;

	for (int i = 1; i < m2; i++) {
		while (command[idx_] != this) {
			command[idx_]->DoThisWork(command, printcount, idx_);
		}

		//루프 문에 다시 도착한 것 이므르 printcount++;을 함
		printcount++;
		idx_ = m1;
	}

	idx++;

	//idx그냥 1증가하는 부분은 여기랑 pass부분 밖에 없으므로 idx가 vector사이즈 넘어가는 검사는 여기에서 함
	if ((unsigned)idx > command.size()) {
		idx = 0;
	}

	return;
}


void Pass::DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const {
	printcount++;

	idx++;

	//idx그냥 1증가하는 부분은 여기랑 loop부분 밖에 없으므로 idx가 vector사이즈 넘어가는 검사는 여기에서 함
	if ((unsigned)idx > command.size()) {
		idx = 0;
	}

	return;
}

void Die::DoThisWork(const std::vector<order*>& command, unsigned long int& printcount, int& idx)const{
	printcount++;

	//예외를 던저서 이 함수를 실행시킨 함수가 있는 반복문을 강제로 끝냄
	throw (printcount);
	
	return;
}

받은 문자열에서 어떤 명령어인지 판단하고 그에 맞는 클래스 반환

//die명령어가 입력이 안됬으면 그냥 infinity 출력하고 끝내기 위해 놔둠
bool thereisdie = false;

//사용자에게 명령어를 입력 받아서 그 입력을 order을 상속하는 클래스로 만듬
order* findorder() {
	using namespace std;

	char orderc[81] = {0};
	string orders;

	fgets(orderc, sizeof(orderc) - 1, stdin);
	orders = orderc;

	//find함수를 한번만 쓰기위해 먼저 명령어의 앞 글자만 봐봄
	char temp;
	int i = 0;
	while ((temp = orderc[i]) < 'a' || temp > 'z')i++;


	int idx;
	int ordername;

	//명령어 앞글자에 따른 find함수 호출, 만약 알맞는 함수가 없다면 강제 종료 시킴
	switch (temp) {
	case 'i' :
		if ( (idx = orders.find("ifgo")) != -1) {
			ordername = IFGO;
			break;
		}
		exit(1);

	case 'j' :
		if ((idx = orders.find("jump")) != -1) {
			ordername = JUMP;
			break;
		}
		exit(1);

	case 'p' :
		if ((idx = orders.find("pass")) != -1) {
			ordername = PASS;
			break;
		}
		exit(1);

	case 'l' :
		if ((idx = orders.find("loop")) != -1) {
			ordername = LOOP;
			break;
		}
		exit(1);

	case 'd' :
		if ((idx = orders.find("die")) != -1) {
			ordername = DIE;
			break;
		}

		exit(1);
	}


	string::size_type j;
	string num1;
	string num2;

	//명령어의 인자를 찾기 위한 스위치
	switch (ordername) {
	case IFGO :
	case JUMP :
	case LOOP :
		
		//첫번째 인자 찾기
		for (j = idx; j < orders.length() && isdigit(orders[j]) == 0; j++);	//받은 문자에서 처음 나온 글자에서 시작해서 처음으로 나온 숫자 찾기

		num1 += orders[j];
		while ((++j) < orders.length() && isdigit(orders[j]) != 0) num1 += orders[j];	//숫자가 한자리수가 아닌 경우 다음글자를 찾아봄 


		switch (ordername) {
		case IFGO :		
			return new Ifgo(atoi(num1.c_str())-1);	//실제 움직여야되는 줄은 0부터 시작하니 -1을 함
			break;

		case JUMP :	
			return new Jump(atoi(num1.c_str())-1);	//실제 움직여야되는 줄은 0부터 시작하니 -1을 함
			break;

		case LOOP :
			// 두번째 인자 찾기

			for (j; j < orders.length() && isdigit(orders[j]) == 0; j++);	//처음 나온 숫자에서 시작해 다음에 나오는 숫자를 찾음

			num2 += orders[j];
			while ((++j) < orders.length() && isdigit(orders[j]) != 0) num2 += orders[j];	//숫자가 한자리수가 아닌 경우 다음글자를 찾아봄 

			return new Loop(atoi(num1.c_str()) - 1, atoi(num2.c_str()));	//실제 움직여야되는 줄은 0부터 시작하니 -1을 함

			break;
		}

	case PASS :			
		return new Pass;
		break;

	case DIE :		
		thereisdie = true;
		return new Die;
		break;
	}

	exit(1);
}

main함수

int main() {
	using namespace std;
	

	vector<order*> commands;		//명령어 넣어둘 vector
	commands.reserve(100000);		//명령어가 최대 100,000이길레 예약해둠

	int loop;
	cin >> loop;
	getchar();

	for (int i = 0; i < loop; i++) {
		commands.push_back(findorder());
	}

	if (thereisdie == false) {
		cout << "infinity";
		return 0;
	}

	int idx = 0;
	unsigned long int printcount = 0ll;
	
	try {
		while (printcount < 1000000000) {
			commands[idx]->DoThisWork(commands, printcount, idx);
		}
	}
	catch (unsigned long int printcount) {
		cout << printcount;
		return 0;
	}

	cout << "infinity";
	return 0;
}

naive한 풀이로는 만점을 받기 힘들어 보입니다. 구현도 좀 더 단순화할 필요가 있습니다.

출처가 있는 문제들은 솔루션까지 제공되는 경우가 있으니, 잘 검색해보시면 정답 소스를 찾으실 수도 있을것 같습니다.

1 Like

직접적인 돌아가는방식을 다이해한건아니지만 일단 제일 먼저 생각나는건 virtual에의한 성능저하로(그렇게 크리티컬하게 영향을 끼치는진 잘모르겠습니다) virtual을 안쓰는 방향으로 다시 짜볼것같네요

1 Like

PS에서 버츄얼 상속+throw 쓰는 것 처음 봤읍니다. 그것들을 빼고 하면 더 낫지 않을까 하는 막연한 추측을 해봅니다.

그거 말고는 std::sync_with_stdio 같은게 생각나기는 하네요. 저라면 얘를 먼저 고려해보고 그래도 안되면 위의 것들을 바꿔볼 것 같네요. 그래도 안되면 알고리즘을 바꿔야지요 ㅎ…

3 Likes

try catch 를 하더라도 exception 이 걸리지 않으면 성능에 큰 문제는 없지만 throw 까지 했다면 기어갈 수 밖에요
다른 부분까지 자세히 보진 않았습니다.

1 Like

이런 문제는 기본적으로 방향그래프로 바꿔서 푸는 거에요. 그냥 쌩 구현하면 당연히 TLE입니다
cycle이 있으면 infinity고 cycle이 없으면 topological sort + DP로 풀면 될 것 같습니다.

5 Likes

저도 방향그래프 같긴한데 그 다음을 한참 고민하고 있었는데,
답변을 들으니 명쾌하네요.
대단하십니다 ㅎㅎㅎㅎ

1 Like