[프로그래머스] 표 편집 [C++][lv.3] 2021 카카오 채용연계형 인턴십

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

프로그래머스

 

 

#문제 간단 정리

 

각 삭제된 상태를 기록하고 인덱스 조회하는 문제

 

#문제 해결 방법

 

가장 쉽게 생각할만 한 것은

삭제됫는지 안 삭제됫는지 표기하기 위해서

배열로 표시하는 것이다.

 

이전에 삭제된 항목은 스택에 기록해두는것.

 

그런데 이렇게 풀게되면 삭제된 항목을 넘어서 그 다음항목을 검색해야 되기 때문에

효율성 테스트에서 실패가 뜨게 된다.

 

때문에 삭제된 항목을 건너 뛸 수 있게

다른 자료구조를 사용해야 되는데

 

연결 리스트를 사용하면 된다.

 

나는 배열로 풀엇다가 

틀려서 연결리스트로 제출했다

 

 

#전체 코드

배열 코드 (실패)

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

 
vector<int> stack;
vector<bool> check;

string solution(int n, int k, vector<string> cmd) {

    check.assign(n, false);
    
    int cur = k;
    
    for(string s : cmd){
        
        char input1 = s[0];
        int input2 = 0;
        if(input1 == 'U' || input1 == 'D')  input2 = stoi(s.substr(2));

        
        if(input1 == 'U'){
            int count = 0;
            while(count != input2){
                if(check[--cur] == false){
                    count++;
                }
            }
        }
        else if(input1 == 'D'){
            int count = 0;
            while(count != input2){
                if(check[++cur] == false){
                    count++;
                }
            }
        }
        else if(input1 == 'C'){
            check[cur] = true;
            stack.push_back(cur);
            
            int temp = cur;
            bool found = false;
            while(temp < n - 1){
                temp++;
                if(!check[temp]){
                    cur = temp;
                    found = true;
                    break;
                }
            }
            if(!found){
                temp = cur;
                while(temp >= 0){
                    temp--;
                    if(!check[temp]){
                        cur = temp;
                        break;
                    }
                }
            }
        }if(input1 == 'Z'){
            check[stack.back()] = false;
            stack.pop_back();
        }
        
    }
    
    
    string answer(n, 'O');
    for (int i = 0; i < n; ++i) {
        if (check[i]) {
            answer[i] = 'X';
        }
    }

    return answer;
}

 

 

연결리스트 코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    vector<int> prev(n), next(n);
    stack<int> removed;
    
    // 초기 링크드 리스트 설정
    for (int i = 0; i < n; ++i) {
        prev[i] = i - 1;
        next[i] = i + 1;
    }
    next[n - 1] = -1;

    int cur = k;
    
    for (const string& s : cmd) {
        char command = s[0];
        int value = 0;
        if (s.size() > 1) value = stoi(s.substr(2));
        
        if (command == 'U') {
            while (value--) {
                cur = prev[cur];
            }
        } else if (command == 'D') {
            while (value--) {
                cur = next[cur];
            }
        } else if (command == 'C') {
            removed.push(cur);
            if (prev[cur] != -1) next[prev[cur]] = next[cur];
            if (next[cur] != -1) prev[next[cur]] = prev[cur];
            
            cur = (next[cur] != -1) ? next[cur] : prev[cur];
        } else if (command == 'Z') {
            int restore = removed.top();
            removed.pop();
            if (prev[restore] != -1) next[prev[restore]] = restore;
            if (next[restore] != -1) prev[next[restore]] = restore;
        }
    }
    
    string answer(n, 'O');
    while (!removed.empty()) {
        answer[removed.top()] = 'X';
        removed.pop();
    }
    
    return answer;
}