이번문제는 혼자서 풀지 못해 해당 글을 보고 풀었습니다...
https://codenme.tistory.com/32
난이도가 상당한거 같습니다..
처음에 틀린코드
#include <iostream>
#include <vector>
#include <algorithm>
#include<memory.h>
#include <string>
using namespace std;
bool graph[1000001];
vector<int>e;
int current = 0;
string solution(int n, int k, vector<string> cmd) {
memset(graph, true, sizeof(graph));
string answer = "";
current = k;
for (int i = 0; i < cmd.size(); i++) {
string commend = cmd[i];
if (commend.size() > 1) {
//U,D
char direction = commend[0];
int amount = 0;
string tmp = "";
for (int x = 2; x < commend.size(); x++) {
tmp += commend[x];
}
amount += stoi(tmp);
int extra = 0;
//D인경우
if (direction == 'D') {
for (int j = 0; j < e.size(); j++) {
if (e[j] <= current + amount && current < e[j]) extra++;
}
current += (amount+extra);
}
else {
//U인경우
for (int j = 0; j < e.size(); j++) {
if (e[j] < current && current -amount <= e[j]) extra++;
}
current -= (amount+extra);
}
}
else if (commend[0] == 'C') {
graph[current] = false;
e.push_back(current);
//마지막인경우
if (current == n-1) {
while (1) {
if (!graph[current]) {
current--;
continue;
}
break;
}
}
else {
while (1) {
if (!graph[current]) {
current++;
continue;
}
break;
}
}
}
else {
//Z인경우
graph[e[e.size() - 1]] = true;
e.erase(e.end()-1);
}
}
for (int i = 0; i < n; i++) {
if (graph[i]) { answer += "O"; }
else {
answer += "X";
}
}
return answer;
}우선 이 문제를 보고 배열로 풀어야겠다는 생각을 했습니다.
U으로 두번을 이동하면 두번 이동할때 false인 인덱스가 있다면 한칸 더 이동하는 방식으로 하였습니다.
C의 경우 vector에다가 넣고, graph를 false로 갱신했습니다.
마지막인 경우: 앞으로 current를 이동하는데 false이면 계속 이동시켰습니다.
마지막이 아닌경우: 뒤로 current를 이동시키는데 false이면 계속 이동시켰습니다.
Z의 경우 그냥 true로 바꾸고 vector에서 지워줬습니다.
그런데 이렇게 하면 시간초과가 발생하는데, 솔직히 시간복잡도를 계산해봐도 왜 그런지는 자세히는 모르겠습니다.
왜냐하면, C와 Z는 O(1)로 해결할수 있고
문제는 U,D인데 중간에 false가 얼마나 있는지 모르니까 계속 움직여야하는건 맞습니다.
근데 노드가 cmd의 X의 합이 1000000 이라했으니까 결국 U,D로 움직이는 연산이 1,000,000번이면 되는데 이게 굳이 시간초과가 뜨는 이유는 모르겠습니다.
해설에서도 이런식으로 밖에 나와있지 않아 잘 이해가 가지 않았습니다.
해결
링크드 리스트를 사용하라 했습니다.
if(c[0] == 'U'){
int num = stoi(c.substr(2,8));
for(int i=0;i<num;i++){
cur = cur -> prev;
}U의 경우 cur을 num만큼 앞으로 땡겨줍니다.
else if(c[0]=='D'){
int num = stoi(c.substr(2,8));
for(int i=0;i<num;i++){
cur = cur -> next;
}D의 경우 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;
}
//마지막노드는 cur을 앞으로 나머지는 cur을 한칸 뒤로
if(cur -> next == NULL) cur = cur -> prev;
else cur = cur -> next;
}C의 경우
그냥 중간에 있는 노드를 삭제한다고 생각해봅시다.
cur -> prev -> next = cur -> next와 cur -> next -> prev = cur -> prev를 해줘야합니다.
그런데 맨 앞의 노드는 cur -> prev가 NULL 이므로 NULL -> next를 통해 세그먼트 fault가 발생할 수 있습니다.
맨 뒤의 노드도 마찬가지 입니다. cur -> next 가 NUll 인데 NULL -> prev를 하면 세그먼트 fault가 발생할 수 있습니다.
그래서 두가지의 조건을 적어주고,
이제 cur을 이동시키면 됩니다. cur의 이동조건은 2가지 입니다.
만약 그냥 이동시키면 되면 cur -> next를 통해서 이동시키고
마지막인 경우는 앞으로 한칸 이동시키면 됩니다.
else{
Node * repair = stk.top();
if(repair -> next != NULL) repair -> next ->prev = repair;
if(repair -> prev != NULL) repair -> prev -> next = repair;
stk.pop();
}Z의 경우도 간단합니다.
repair -> next -> prev = repair을 해줘야합니다. 그런데 생각해보면 여기도 repair -> next가 없을 수 있습니다. 언제? 마지막 노드일때
repair -> prev도 마찬가지입니다. 맨 앞의 노드의 경우 NULL이 발생합니다. 고로 해당 조건을 적고 pop을 해줍니다.
실제 시험장에서 풀라하면, 아마 segment fault때문에 콘솔에 찍어보지도 못하고 아마 절대 못풀었을 거 같습니다.
이걸 연결리스트로 풀 생각을 하기보다는, 일단 정확성이라도 맞출수 있는 실력을 기르는게 중요한거 같습니다..
