프로그래머스. 표 편집

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

 

이 문제는 테스트케이스 변경으로 더이상 아래 방법인 c++ stl <set> 자료구조를 사용해서 풀수 없다. 

다시 푼 링크 : https://tose33.tistory.com/662

 

 

 

---

주어지는 행의 갯수가 최대 100만개, 명령이 20만개이다. 

벡터는 원소를 지웠을때 지운 원소 뒤의 모든 원소들을 한칸씩 땡기므로 최대 O(n)의 시간이 소요되므로 이 문제에는 적절치 않다.

이렇게 원소를 지우거나 추가하는 연산이 많을때는 연관 컨테이너를 쓰는게 좋아보인다. 

이 문제에서는 set을 이용했는데 풀다보니까 "삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.", "가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다."

이런 조건 들을 보면 set 자료구조를 염두해두고 만든 문제인것 같았다.

 

1. 행들을 set에 insert 한다.

2. iterator를 k만큼 이동시킨다.

3. 명령을 처리한다.

    U X: iterator를 X만큼 --

    D X: iterator를 X만큼 ++

    C: iterator가 가르키고 있는 값을 vector에 푸쉬해놓고, iterator가 가르키는 지점을 erase한다.

         이때 it = set.erase(it) 이런식으로 해야 iterator가 다음 지점을 가르킨다. 

    Z: 지우는 연산에서 저장해놓은 백터의 마지막값을 set에 insert 한다. 

        해당 값은 벡터에서 제외한다.