[틀림] 프로그래머스 표편집 c++ // 연결리스트 직접구현 하는방법, 삽입삭제 되돌리기는 연결리스트(직접구현)!

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

프로그래머스

1. 고찰

stl의 list<int>를 쓰면 풀수없는듯 하다.

이유 : prev,next 가 없음..

- 삽입삭제, 되돌리기는 연결리스트(직접구현)!

- 삭제된 노드도 prev,next가 남아있기때문에 복원이 ez하다!

 

2.전체코드

#include <bits/stdc++.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){}
        
};

//(삽입,)삭제가 빈번할때는 리스트!
//행갯수n , 첫인덱스 k
string solution(int n, int k, vector<string> cmd) {
    string answer(n,'X'); //n만큼 X로 채우기
    
    //노드연결
    Node* cursor = new Node(0,NULL,NULL); //첫노드
    for(int i=1;i<n;++i){
        cursor->next=new Node(i,cursor,NULL);
        cursor=cursor->next;
    }
    
    // k로 커서 이동
    //n=4, k=1 일때 : 0 , 1, 2, 3
    //3에서 1로 2회이동해야함
    //2회==n-k-1회
    for(int i=0;i<n-k-1;i++) cursor = cursor->prev;
    
    stack<Node*> del;
    for(auto op : cmd){
        if(op[0]=='U'){
            //if(k==0) continue;
            int x=stoi(op.substr(2));
            while(x--) cursor=cursor->prev;
        }
        else if(op[0]=='D'){
            //if(k==n-1) continue;
            int x=stoi(op.substr(2));
            while(x--) cursor=cursor->next;
        }
        else if(op=="C"){
            del.push(cursor); //삭제할노드 포인터 넣기
            //앞노드가 있는경우 , 그림그려보면 쉬움
            if(cursor->prev != NULL) cursor->prev->next=cursor->next; // < -연결
            if(cursor->next!=NULL) cursor->next->prev = cursor->prev; // -> 연결
            
            //마지막노드인경우 이전노드 가르키도록
            if(cursor->next==NULL) cursor = cursor->prev;
            else cursor = cursor->next; //마지막노드가아니면 다음노드를 가르킴
            
        }
        else if(op=="Z"){
            auto r = del.top(); del.pop();
            if(r->prev != NULL) r->prev->next=r; // -> 다시연결
            if(r->next != NULL) r->next->prev=r; // <- 다시연결
        }
    }
    
    //정답채우기
    answer[cursor->n]='O';
    // <-로 가면서 살아있는 idx에 O 채우기
    while(cursor->prev!=NULL){
        answer[cursor->prev->n]='O';
        cursor=cursor->prev;
    }
    // ->로 가면서 살아있는 idx에 O 채우기
    while(cursor->next!=NULL){
        answer[cursor->next->n]='O';
        cursor=cursor->next;
    }
    
    return answer;
}

 

 

* 25.5.9. 2회독

시도1

자바가 제공하는 링크드 리스트로 구현?

안되는이유 : cursor(현재위치) 를 찾기위해서 O(N)이 걸림 -> 직접 구현해야함

시도2

배열 && soft delete?

삭제시) 마지막행인지 보려면 O(N)이 필요함. -> 팬윅트리, 세그트리로 개선가능 하다고 함.

풀이( 직접구현한 양방향 연결리스트)

1. 링크드 리스트 만들기

2. 크게 3가지 경우로 나누어 생각 : 맨앞, 맨뒤, 중간

복구시 삭제된 노드의 포인터가 살아있음을 이용해 O(1)만에 복구가능!

3. 정답을 만들기위해 removed 필드추가, 배열에 담아놓기

전체코드

import java.util.*;

class Node {
    int val;
    boolean removed;
    Node prev,next;
    
    Node(int val, boolean removed, Node prev, Node next){
        this.val=val;
        this.removed=removed;
        this.prev=prev;
        this.next=next;
    }
    
    void setPrev(Node prev){
        this.prev=prev;
    }
    
    void setNext(Node next){
        this.next=next;
    }
}

class Solution {
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        
        Node [] arr = new Node[n];
        
        Node first = new Node(0,false,null,null);
        Node prev=first;
        arr[0]=first;
        
        for(int i=1;i<n;++i){
            Node node = new Node(i,false,null,null);
            arr[i]=node;
            prev.setNext(node);
            node.setPrev(prev);
            prev=node;
        }
        
        Node cursor=first;
        while(k-- > 0){
            cursor = cursor.next;
        }
        System.out.println(cursor.val);
        // while(cursor.next!=null){
        //     System.out.println(cursor.val);
        //     cursor = cursor.next;
        // }
        // System.out.println(cursor.val);
        
        Stack<Node> stk = new Stack<>();
        
        for(String op : cmd){
            if(op.charAt(0)=='U'){
                int x = Integer.parseInt(op.substring(2)); //주의 : x는 30만 이하임. 한자리 아님!, 2~끝까지
                while(x-- >0){
                    cursor = cursor.prev;
                }
            }
            else if(op.charAt(0)=='D'){
                int x = Integer.parseInt(op.substring(2));
                while(x-- >0){
                    cursor = cursor.next;
                }
            }
            else if(op.charAt(0)=='C'){
                cursor.removed=true;
                stk.push(cursor);
                if(cursor.next==null){ //막행인경우
                    cursor = cursor.prev;
                    cursor.next=null;
                }
                else if(cursor.prev==null){ //첫행인경우
                    cursor = cursor.next;
                    cursor.prev=null;
                }
                else{
                    cursor.prev.next = cursor.next;
                    cursor.next.prev = cursor.prev;
                    cursor = cursor.next;
                }
            }
            else if(op.charAt(0)=='Z'){
                Node node = stk.pop();
                node.removed=false;
                
                if(node.next==null){ //막행인경우
                    node.prev.next=node;
                }
                else if(node.prev==null){ //첫행인경우
                    node.next.prev=node;
                }
                else{
                    node.prev.next=node;
                    node.next.prev=node;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;++i){
            if(arr[i].removed==true){
                sb.append("X");
            }
            else{
                sb.append("O");
            }
        }
        
        return sb.toString();
    }
}

 

헤맸던 부분

이동할 칸수 X는 한자리가 아님, 30만까지가능 -> substring(2) //2~끝까지로 추출해야함.

정답은 어떻게 만들지? -> 배열에 노드를 넣어놓고 removed를 체크.