https://school.programmers.co.kr/learn/courses/30/lessons/81303
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
위의 문제에 대한 해설입니다.
우선 문제의 효율성 테스트를 통과하려면 꽤 큰 input에도 대처가 가능해야하는데, 이 때문에 문제 그대로 단순히
삽입, 삭제를 그때 그때 수행하는 것 만으론 시간복잡도가 오버된다.
따라서 삽입, 삭제를 실제로 행하지 않거나, 혹은 실제로 삽입, 삭제를 진행하되, 그 효율을 좋게 만들어야만 해결할 수 있다.
내 경우는 linked list 자료구조를 통해 해결했다. linked list 자료구조의 경우, sequential한 탐색이 아니라면
적합하지 못한 자료구조이고, vector, queue,stack과 같이 c++ 헤더를 통해 가져올 수 없다.
다만 삽입, 삭제의 경우, 삽입, 삭제 위치를 구할 필요가 없다면, O(1)으로 해결 가능하다.
이 문제는 '현재 위치' 에서의 삽입, 삭제에 관한 문제이므로 linked list가 적합하다고 볼 수 있다.
추가로 'Z' 명령어를 구현하여 최근 삭제된 노드를 복구할 수 있어야하는데, 이는 stack 자료구조를 사용하여 지운 노드를 저장하는 것으로 최근 삭제된 순서대로 복구가 가능하도록 구현하였다.
여기서 linked list 자료구조의 강점을 또 다시 활용하는데, 삭제된 링크드 리스트는, 삭제되기전에 보유하고 있던
previous_node의 정보와 next_node의 정보를 그대로 가지고 있기에, 만약 'Z' 명령어로 복구해야될 경우, 복구할 위치를 찾아서 삽입할 필요 없이, 기존에 보유한 이전 노드, 다음 노드 정보를 기반으로 O(1)의 시간 복잡도로 복구가 가능하다.
#include <string>
#include <vector>
#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
struct Node { // 양방향 연결 리스트
int n;
Node* prev;
Node* next;
Node(int n, Node* prev, Node* next) : n(n), prev(prev), next(next) {} //생성자
};
stack<Node*> stk; //삭제된 노드를 저장하는 stack 자료구조
string solution(int n, int k, vector<string> cmd) {
//string answer = "";
string answer(n, 'X');
Node* it = new Node(0, NULL, NULL); //각 개체는 생성 후 개별적인 객체로 유지됨. 포인터로 가르켜야한다 .
Node* cur; //현재 위치를 가르키는 포인터.
for (int i = 1; i < n; i++) {
it->next = new Node(i, it, NULL);
it = it->next;
if (i == k)
cur = it;
}
for (auto c : cmd) {
if (c[0] == 'U') {
int num = stoi(c.substr(2, 8));
while (num--) cur = cur->prev;
}
else if (c[0] == 'D') {
int num = stoi(c.substr(2, 8));
while (num--)cur = cur->next;
}
else if (c[0] == 'C') {
stk.push(cur);
if (cur->prev != NULL) cur->prev->next = cur->next;
if (cur->next != NULL) cur->next->prev = cur->prev;
if (cur->next == NULL) cur = cur->prev;
else cur = cur->next;
}
else if (c[0] == 'Z') {
if (!stk.empty()) {
Node* tmp = stk.top();
if (tmp->prev != NULL) tmp->prev->next = tmp;
if (tmp->next != NULL) tmp->next->prev = tmp;
stk.pop();
}
}
}
while (cur->prev != NULL)cur = cur->prev; //첫번째 연결 리스트로 위치 이동.
while (cur != NULL) { //시작~ 끝 완전탐색.
answer[cur->n] = 'O'; //삭제되지 않은 노드들을 표시한다.
cur = cur->next;
}
return answer;
}