[Programmers] 표 편집

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/81303

프로그래머스

문제의 특성상 삽입, 삭제가 O(1)에 이루어져야 하므로 링크드 리스트 자료구조를 통해 푸는 문제였습니다.

c++에서는 stl로 list를 제공하기는 하나 많이 써본 경험이 없으므로 이중 연결 리스트를 직접 구조체를 구현하여 풀었습니다.

이중 연결리스트에 관한 자세한 코드는 아래의 링크를 참고해주세요.

https://jaimemin.tistory.com/169

C++ Fundamentals of Data Structures(C++ 자료구조론) 4.10 이중연결리스트(Doubly Linked List)

 

알고리즘은 아래와 같습니다.

1. 이중 연결리스트를 구현하고 현재 주어진 표를 전 처리합니다.

2. iterator 변수를 선언하고 k번째 노드를 가리키도록 합니다.

3. Z 명령어가 최근 삭제된 행을 원래대로 복구하는 명령어이므로 스택을 써야 합니다. 따라서 deletedNodes 스택을 선언해줍니다.

4. 주어진 명령어대로 표 편집을 진행합니다.

5. 표 상태를 나타내는 answer를 업데이트해주고 반환해줍니다.

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~