[회고록]vector와 list의 삽입, 제거 연산

vector는 안되고 list는 된다?

백준의 에디터 문제 지문을 읽다가 어려운 문제가 아니라서 “vector 자료구조를 이용하면 그냥 풀리겠네?” 라고 생각하고 제출을 했더니 보기좋게 시간초과 판정을 받았다. 분명 문제풀이는 맞았다. 하지만 그에 드는 시간복잡도가 매우 컸다.

곰곰히 생각해 보니 예전에도 이런 비슷한 상황을 겪은 적이 있었다. 이처럼 문자를 다루는 문제였고 똑같이 vector를 사용하면 해결될 문제같았지만 시간초과가 되어 stack 자료구조로 시간복잡도를 최저로 잡아 풀었었다. 정확히 무엇이 문제였느냐. 그건 바로 vector 라는 자료구조 자체에 있다. vector는 배열처럼 연속되는 주소체계를 가지고 있다. 그래서 다음과 같은 연산이 가능하다.

vector<int>::iterator iter = v.begin();
.
.
iter = iter + 1;

마치 배열처럼 다음 원소의 위치를 1칸 단위로 접근할 수가 있다. 자료구조를 공부해 보았다면 배열의 단점을 알고 있을 것이다. 연속된 주소체계를 가지고 있기 때문에 ‘중간에 하나의 원소’를 추가하거나 지우려면 큰 비용을 감수해야한다. 10개의 원소 에서 2번째 원소를 없앤다면 3 ~ 10번째에 있던 원소들은 왼쪽으로 한칸씩 전부 옮겨야 한다. 10개의 원소에서 2번째 자리에 원소를 추가하고자 하면 원래 2번째 ~ 10번째에 있던 원소들은 오른쪽으로 한칸씩 옮겨야 한다. 감이 잡힐 것이다. 원소 갯수가 많으면 많을 수록 그 비용은 점점 더 막대해 진다. 가장 뒤에 있는 원소를 지우면 상관없겠지만 여기서는 ‘중간의 원소’에 초점을 맞춘 것이다. 하지만 방법이 있다. List 자료구조를 사용하면 된다.

List는 배열의 주소체계와는 다르게 요소 하나를 link(연결)해서 자료구조를 유지한다. 연속된 주소체계가 아니기 때문에 다음과 같은 연산은 불가하다.

list<int>::iterator iter = l.begin();
.
.
iter = iter + 1;

될 듯 싶지만 안된다. 하지만 유심히 생각해보면 list는 연속된 주소체계를 가지는 자료구조가 아니기 때문에, +1 이라는 것은 연속된 주소체계상에서 바로 오른쪽에 있는 요소에 접근하겠다는 것으로 이해할 수 있다. list는 순차적인 자료구조가 아닌 연결 자료구조 이기 때문에 이와 같은 연산은 불가하다. 그렇기에 연결 리스트에서 다음 원소에 접근하려면 다음과 같이 접근해야 한다.

list<int>::iterator iter = l.begin();
.
.
iter++;

언뜻 보면 iter = iter + 1 이랑 차이가 없어 보이지만 이곳에서의 ++ 연산자는 연결 리스트 상에서 다음 요소의 위치를 가리킬 수 있게 된다. 또한 vector와는 다르게 중간 원소를 추가하거나 제거하면 오른쪽에 있던 원소들을 왼쪽으로 한칸씩 전부 끌어오는게 아니라 그냥 link를 삭제된 원소의 다음 원소에게 새로 연결해주면 된다. 애초에 빈 공간이라는 개념 자체가 생기지가 않게 되는 것이다.