40번 교집합 문제

Question

선생님, 제가 이 방법으로 처음에 풀었었는데 알고리즘 상으로는 1초안에 들어오는 방법인가요?? 맞다면 c배열의 범위를 어떻게 지정해야되는지 잘 모르겠어서 질문드립니다!(stdio.h랑 vector는 위에서 선언했습니다)

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. dongdong님 질문에 답변 드리겠습니다. 제시하신 코드는 두 개의 벡터 a 와 b 에서 공통된 원소를 찾아내는 알고리즘으로 보입니다. 이 방법의 시간 복잡도는 입력되는 n 과 m 의 크기에 따라 다르며, 주어진 조건에서는 대체로 1초 안에 실행될 수 있으나, n 과 m 의 최댓값에 따라 다릅니다. c 배열의 범위는 a 와 b 배열에 있는 수의 최댓값에 따라 결정됩니다. 만약 a 와 b 에 들어갈 수 있는 수의 범위가 한정되어 있다면(예: 1부터 1000까지), c 배열의 크기도 그에 맞춰 설정할 수 있습니다. 그러나 입력 값의 범위가 넓을 경우, 더 큰 배열을 선언하거나 다른 방법을 고려해야 할 수 있습니다. 또한, 공간 복잡도를 줄이기 위해서는 해시 테이블(예: std::unordered_map )을 사용하는 방법도 고려해볼 수 있습니다. std::unordered_map 을 사용하면 다양한 범위의 수들을 효과적으로 관리할 수 있으며, c 배열의 크기를 크게 설정할 필요가 없어지게 됩니다. 결론적으로, 제시하신 코드의 효율성은 주로 입력 크기와 c 배열의 적절한 범위 설정에 달려 있습니다. 입력되는 수의 최댓값을 아신다면, c 배열은 그에 맞춰 크기를 설정하시면 됩니다. 그러나 최댓값이 크거나 불명확할 경우에는 해시 테이블 사용을 고려해보세요.