우선 source style 의 호불호를 떠나서 it++ 부분은 전반적으로 권장되지 않는 것으로 알고 있습니다.
vector 의 iterator 는 pointer 에 가깝기 때문에 그래도 괜찮지만 list 의 iterator 는 그런 최적화가 어렵죠.
독립적인 문장에서 쓰시는 거라면 ++it 을 쓰시고, tempit 과 관련된 부분은 tempit = it++ 로 두 문장을 한 문장으로 묶으시는 것도 괜찮을 것 같습니다.
먼저 확인차 여쭤보자면 vector 를 가지고 pop_front 를 하셨다는 말씀은 v.erase(v.begin()) 을 하셧다는 말씀인가요?
그게 맞다면 통상적으로 vector 의 특성상 많은 시간을 요구하는 작업인 것은 맞습니다.
원소의 할당 및 해제 속도는 원소 형식, 여기서는 ele 의 크기 및 특성도 영향을 많이 받을 것 같습니다.
또한 할당을 할 때 push_back 을 쓰는 거라면 node 기반 container 인 list 는 vector 에 비해서 느릴 수 밖에 없고요.
동적할당과 해제는 내부적으로 복잡한 과정을 거치기 때문에 응용에서 드러나는 시간복잡도와는 다른 결과를 보여줄 수 있다는 점도 염두하시기 바랍니다.
rlaalswo01 6년 전
코드 첨부했습니다. 코드를 조금 장황하게 짜는 스타일인 것 같아 보시는데 불편하시다면 죄송합니다 ㅠㅠ
질문의 요지는 왜 벡터의 erase가 list의 erase보다 빠른가? 입니다.
세 가지 방법으로 풀어 제출해봤는데요.
방법 1.입력으로 들어오는 진영을 모두 벡터에 담는다. -> 벡터를 순차적으로 탐색하여, visited 배열에 표시가 안된 원소라면 visited 배열에 표시하고 해당 원소를 리스트에 담는다. 이때 cnt 1 증가. -> 리스트는 empty가 될 때까지 매번 벡터의 처음부터 끝까지 탐색하여 front와 연락이 가능한 원소들을 push_back 하며 visited 배열에 표시를 하고 pop_front. 즉 최악의 경우 테스트 케이스 당 입력벡터의 최대사이즈 3000의 제곱 탐색을 할 것으로 예상.
이 방법으로 문제를 풀었을 때, 약 1600 MS 의 소요시간으로 문제를 풀었습니다.
이 다음의 저의 생각은, 이미 연락 그룹에 속해버린 원소들은 입력받은 벡터에서 제거하면 탐색량을 줄일 수 있어 소요시간 또한 줄일 수 있겠다는 생각을 하였습니다. 하지만 벡터의 erase 보다는 리스트의 erase가 효율적일 것으로 생각하여 첨부한 코드처럼 문제를 해결해 보았습니다.
방법 2. 방법 1과 같은 방식이지만 입력을 벡터에 담지 않고 리스트에 담는다. -> 입력 리스트가 비어있지 않다면 입력 리스트의 front를 임시리스트에 담고 입력 리스트에선 제거. 이때 cnt 1 증가. -> 임시 리스트의 front와 연락이 되는 원소를 입력리스트의 처음부터 끝까지 탐색하여 push_back 하며 동시에 입력 리스트에서는 erase. 입력 리스트가 비어있지 않다면 반복.
하지만 이 코드는 2000 MS 가 넘는 더 많은 시간을 소요하여 문제를 해결했습니다.
방법 3.그리고 첨부한 코드와 같은 방식이지만 다시 벡터에 입력진영들을 담고 벡터가 빌때까지 erase하며 원소들을 제거해나가니 약 600MS 로 문제가 해결되었습니다. 일반적으로 자료구조를 배울때 리스트의 장점은 중간 삽입, 제거가 빠르다는 것인데 왜 이런 결과가 나오는지 궁금합니다.