글 읽기 - c++ 시간초과 질문입니다 (list 사용)

dudwls901 3년 전 0

list 컨테이너 사용해서 구현했습니다.

처음 개구리의 위치 x,y

(x+y)%2가 같은 것들만 입력을 받게 필터링했습니다.

그 후 잎의 위치 a,b

a와 x의 차이 == b와 y의 차이가 같은 것중에
차이가 적은 것으로 이동하게끔 구현했는데

어느 부분이 비효율적인지,

어떻게 시간을 단축시킬 수 있는 지 봐주세요ㅜ

#include <iostream>
#include<list>
#include<string>


using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	
	cin >> n >> k;
	string dir;
	cin >> dir;
	list<int> lix,liy;
	int x, y;
	while (n--) {
		int a, b;
		cin >> a >> b;
		if (lix.empty() && liy.empty()) {//처음 개구리의 위치
			x = a;
			y = b;
			lix.push_back(a);
			liy.push_back(b);
		}
		else {
			if ((x + y) % 2 == (a + b) % 2) {
				lix.push_back(a);
				liy.push_back(b);
			}
		}
		
	}
	
	lix.pop_front();
	liy.pop_front();

	for (int i = 0; i < dir.length(); i++) {
	
		if (dir[i] == 'A') {// x++ y++
			list<int>::iterator xi,yi;
			list<int>::iterator a, b;
			int dif = 1111111111;
			for (xi = lix.begin(),yi= liy.begin(); xi != lix.end(); xi++,yi++) {
				if (*xi < x || *yi < y)
					continue;
				if (*xi - x == *yi - y) {
					if (dif > *xi - x) {
						dif = *xi - x;
						a = xi;
						b = yi;
					}
				}
			}
			if (dif == 1111111111)
				break;
			else {
				x = *a;
				y = *b;
				lix.erase(a);
				liy.erase(b);
			}
		}
		else if (dir[i] == 'B') {// x++ y--
			list<int>::iterator xi, yi;
			list<int>::iterator a, b;
			int dif = 1111111111;
			for (xi = lix.begin(), yi = liy.begin(); xi != lix.end(); xi++, yi++) {
				if (*xi < x || *yi > y)
					continue;
				if (*xi - x == y- *yi) {
					if (dif > *xi - x) {
						dif = *xi - x;
						a = xi;
						b = yi;
					}
				}
			}
			if (dif == 1111111111)
				break;
			else {
				x = *a;
				y = *b;
				lix.erase(a);
				liy.erase(b);
			}
		}
		else if (dir[i] == 'C') {// x-- y++
			list<int>::iterator xi, yi;
			list<int>::iterator a, b;
			int dif = 1111111111;
			for (xi = lix.begin(), yi = liy.begin(); xi != lix.end(); xi++, yi++) {
				if (*xi > x || *yi < y)
					continue;
				if (x - *xi == *yi - y) {
					if (dif > *yi - y) {
						dif = *yi - y;
						a = xi;
						b = yi;
					}
				}
			}
			if (dif == 1111111111)
				break;
			else {
				x = *a;
				y = *b;
				lix.erase(a);
				liy.erase(b);
			}
		}
		else if (dir[i] == 'D') {// x-- y--
			list<int>::iterator xi, yi;
			list<int>::iterator a, b;
			int dif = 1111111111;
			for (xi = lix.begin(), yi = liy.begin(); xi != lix.end(); xi++, yi++) {
				if (*xi > x || *yi > y)
					continue;
				if (x - *xi  == y - *yi) {
					if (dif > x - *xi ) {
						dif = x - *xi;
						a = xi;
						b = yi;
					}
				}
			}
			if (dif == 1111111111)
				break;
			else {
				x = *a;
				y = *b;
				lix.erase(a);
				liy.erase(b);
			}
		}


		}
		cout << x << ' ' << y;
	return 0;
}

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

문제

문제

출처

ICPC

c++ 시간초과 질문입니다 (list 사용)

dudwls901 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말