인프런 커뮤니티 질문&답변

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2-P

2-P 얕은 복사를 이용한 풀이에 대해 질문드립니다!

해결된 질문

작성

355

수정됨

안녕하세요 큰돌님! 항상 좋은 강의 감사드립니다!

다름이 아니라 제가 이 문제를 풀 때 원본은 그대로 유지하고 원본을 이용해서 테스트 케이스마다 copy()랑 배열의 주소값를 이용해서 얕은 복사로 풀이했습니다! 이렇게 풀이해도 괜찮을까요?

검색을 해보니 copy()의 시간복잡도가 O(n)이라고 나오는데 그러면 매번 복사를 하다 보면 시간복잡도가 늘어날 것 같다는 생각이 들더라고요! 제 풀이의 시간복잡도를 계산해 보면

64C3 * (64 + 64 + 64) 인 것인가요?

답변 1

지식공유자

안녕하세요 종인님 ㅎㅎ

일단 copy는 얕은 복사가 아닙니다. 깊은 복사이기 때문에 copy를 한 이후 arr와 arr_dist는 서로 상관없는 배열이 됩니다.

copy의 시간복잡도는 O(N)이 맞으며 시간복잡도 계산도 맞습니다. copy는 상관없으나 이부분을 좀 더 효율적으로 하시면 좋을 거 같아요.

				for (int a = 0; a < n; a++) {
					for (int b = 0; b < m; b++) {
						if (arr_dst[a][b] == 2) dfs(a, b);
					}
				}

바이러스 퍼트릴 때 바이러스 지점에서 퍼트리는데 지점 같은 경우는 충분히 맵을 입력받을 때 계산될 수 있기 때문에 해당 부분만 더 고려해주신다면 더 좋은 코드가 될 것같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

감사합니다.

강사 큰돌 올림.

질문자

지점은 맵을 입력받을 때 계산이 가능했군요..!! 해당 부분을 고쳐봐야겠네요:) 답변 감사드립니다!

작성한 질문수