https://chanheess.tistory.com/154
vector와 list의 차이점
vector 연속적인 메모리. 미래에 들어갈 요소를 위해 선할당을 한다 각 요소는 요소 타입 그자체만큼의 공간을 요구한다 (포인터들을 포함하지 않는다). 당신이 요소를 추가하는 어느 때나, 전체 v
chanheess.tistory.com
위 글에 정리가 잘 되어있다.
https://www.acmicpc.net/problem/1406
1406번: 에디터
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수
www.acmicpc.net
위 문제에서 vector를 사용해 insert, erase연산으로 요소를 중간에 삽입/삭제 한다면 원소 이동 비용이 커 시간 초과가 난다.
또한, deque를 사용해 insert, erase연산을 해도 시간 초과가 난다. => vector보다 빠르긴 한데 왜 시간초과 나는지 모르겠음...
C++의 list는 doubly linked list이기 때문에 삽입/삭제 비용이 vector에 비해 적다.
그러므로 list를 이용해 구현하면 시간초과가 나지 않는다.
근데 이 문제 시간 적게 걸린 사람들은 string을 많이 썼더라...이건 생각도 못했네
물론 stack도!
'CS > C++' 카테고리의 다른 글
| C++로 BFS, DFS 구현 (0) | 2023.08.09 |
|---|---|
| C++ 정수, 실수 자료형 범위와 주의할 점 (0) | 2023.07.21 |
| C++ Deque VS Vector (0) | 2023.07.12 |
| C++로 덱 구현 (0) | 2023.07.11 |
| C++로 큐 구현 (0) | 2023.07.11 |