리스트

[프로그래머스 level 3] 표편집 (C++)

카카오 2021 인턴 삽입, 삭제의 시간이 O(1)이거나 O(logn)이면 풀 수 있을 것 같았다. (알고보니 이동시간이 더 중요했다) log시간을 쓰려면 세그먼트 트리를 써야 할 것 같아서 너무 복잡해질게 예상되어서 그쪽으로는 시도하지 않았다. 예전에 백준에서 풀었던 'AC'문제랑 비슷하다고 생각했다. 그리고 학교 자료구조 시간에 리스트 과제 문제와 비슷했다. 처음에 리스트를 사용해 푸는 거라고 생각해서 List STL을 사용해서 시도해 보았다. STL에 있는 List는 삽입, 삭제는 O(1)이지만, 문제의 'U', 'D', 'Z' 명령어를 처리할 수가 없었다. 키 포인트 Z를 수행하기 위해서는 삭제된 행의 순서를 스택에 입력해 놓아야 한다. C는 리스트에서 값을 지우는 척만 하고 실제로 지워서는 안 ..