글 읽기 - 맞았지만 vector 사용 관련해서 질문있습니다!!

wony6731 4년 전 0

저는 상어를 vector를 통해 관리를 해주면서 잡아먹혔을경우 erase함수를 이용하여 제거해줍니다.

여기서 여쭤볼게 erase를 쓰면 시간이 많이 걸린다는 말을 들은 것 같아서...

알고리즘을 푸는데 vector.erase를 쓰는 것이 좋지 않은 습관인가요...? ㅜㅜ

#include <iostream>
#include <vector>

using namespace std;

struct Shark {
	int x, y, size, speed, dr;
};
int board_x, board_y, shark_cnt;
int sum = 0;
int board[100][100];
vector<Shark> sharks;
int dx[5] = { 0, 0, 0, 1, -1 };
int dy[5] = { 0, -1, 1, 0, 0 };

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> board_y >> board_x >> shark_cnt;

	// 행, 열, 속력(s), 이동방향, 크기
	for (int i = 0; i < shark_cnt; i++){
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		struct Shark shark;
		shark.dr = d;
		shark.speed = s;
		shark.size = z;
		shark.x = c - 1;
		shark.y = r - 1;
		sharks.push_back(shark);
		board[shark.y][shark.x] = 1;
	}

	// Implementation
	int man_location = -1;
	while (true){
		// 오른쪽으로 한 칸 이동
		man_location++;
		if (man_location >= board_x)
			break;

		// 상어잡기
		for (int i = 0; i < board_y; i++){
			if (board[i][man_location] == 1){
				for (int j = 0; j < sharks.size(); j++){
					if (sharks[j].x == man_location && sharks[j].y == i){
						sum += sharks[j].size;
						sharks.erase(sharks.begin() + j);
						board[i][man_location] = 0;
						break;
					}
				}
				break;
			}
		}

		// 상어이동
		for (int i = 0; i < board_y; i++)
			for (int j = 0; j < board_x; j++)
				board[i][j] = 0;
		for (int i = 0; i < sharks.size(); i++){
			// 상어 이동
			int cnt = sharks[i].speed;
			// 제자리로 돌아오는 값 줄이기
			if (sharks[i].dr == 1 || sharks[i].dr == 2)
				cnt = cnt % ((board_y - 1) * 2);
			else
				cnt = cnt % ((board_x - 1) * 2);

			// 상어 이동
			while (cnt--){
				sharks[i].x += dx[sharks[i].dr];
				sharks[i].y += dy[sharks[i].dr];

				if (sharks[i].x < 0){
					sharks[i].x = 1;
					sharks[i].dr = 3;	// 오른쪽
				}
				else if (sharks[i].x >= board_x){
					sharks[i].x = board_x - 2;
					sharks[i].dr = 4;	// 왼쪽
				}
				else if (sharks[i].y < 0){
					sharks[i].y = 1;
					sharks[i].dr = 2;	// 아래
				}
				else if (sharks[i].y >= board_y){
					sharks[i].y = board_y - 2;
					sharks[i].dr = 1;	// 위
				}
			}

			// 상어가 없으면
			if (board[sharks[i].y][sharks[i].x] == 0){
				board[sharks[i].y][sharks[i].x] = 1;
			}
			// 상어가 있으면
			else{
				// 기존에 있는 상어 찾기
				for (int j = 0; j < i; j++){
					if (sharks[j].y == sharks[i].y && sharks[j].x == sharks[i].x){
						// 상어의 크기 비교하여 잡아먹기
						if (sharks[i].size < sharks[j].size)
							sharks.erase(sharks.begin() + i);
						else
							sharks.erase(sharks.begin() + j);
						i--;
						break;
					}
				}
			}
		}
	}

	cout << sum << "\n";

	return 0;
}

sbrus_1213 4년 전 1

document를 찾아보니 vector::erase는 linear(O(n)) 시간 복잡도를 갖는다고 나와있네요

만약 2중 for문에서 사용하시면 전체 시간복잡도 가 n^3꼴로 돼서 그렇게 말하는 거서 같습니다.

다큐먼트 링크 첨부하겠습니다.

https://en.cppreference.com/w/cpp/container/vector/erase

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

문제

문제

출처

ICPC

맞았지만 vector 사용 관련해서 질문있습니다!!

wony6731 4년 전 0

sbrus_1213 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말