[프로그래머스] 표편집 2021 카카오 인턴십 STL(set)

문제 : 

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

코딩테스트 연습 - 표 편집

 

분석 : 

주어진 표 정보를 벡터에 담아 erase, insert등 기본 STL 방식으로 접근했었다. 테스트 케이스는 맞았으나 정확성 테스트, 효율성 테스트에서 segmentation fault 에러를 받았고 벡터 공간을 지우고 다시 삽입하는 과정에서 인덱스 범위를 넘어서는 것 같은 오류를 범한거 같다. 그래서 블로그를 참고하니 set이 원소를 넣을 때마다 자동적으로 오름차순 정렬되어 들어 간다는 사실을 알게 되었다 ..! 

그래서 기존 코드를 담는 그릇을 set으로 바꾸었고 iterator를 이용해 U, D, C, Z 시 인덱스를 적절하게 움직여 주었다. 

 

틀린 접근 코드 : (vector 이용)

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

using namespace std;

vector<int> reV;
stack<pair<int, int>> s;

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    for(int i = 0; i < n; i++){
        reV.push_back(i);
    }
    
    
    int moving = k;
    vector<int>::iterator nowArray = reV.begin();
    
       for(int i =0; i < cmd.size(); i++){
           nowArray = reV.begin() + moving; // 현재 위치 값 2
               //c cmd 수행
               if(cmd[i] == "C"){// 삭제
                   s.push({moving, *nowArray});// 삭제 인덱스, 원소 값
                   reV.erase(nowArray);
                   //reV.resize(n);
                   if(*nowArray == 7){ // 마지막
                       moving -=1;
                   }
                   continue;
            	//z cmd 수행
               }else if(cmd[i] == "Z"){
                  
                   if(!s.empty()){
                       int index = s.top().first;
                       int value = s.top().second;
                       reV.insert(reV.begin() + index , value);
                       if(index < moving){
                           moving += 1;
                       }
                       s.pop();
                   }
                   continue;
                   
               }else{
                   if(cmd[i][0] == 'D' && (48 <= cmd[i][2] &&  cmd[i][2] <= 57)){
                        moving += cmd[i][2] - '0';
                   }else if(cmd[i][0] == 'U' && (48 <= cmd[i][2] &&  cmd[i][2] <= 57)){
                        moving -= cmd[i][2] - '0';
                   }
            }
          
       }
    answer = "OOOOOOOO";
    while(!s.empty()){
        answer.at(s.top().first) = 'X';
        s.pop();
    }


    return answer;
}

 

c++ 코드 : (set 이용)

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

using namespace std;

//vector<int> reV;
set<int> ss;


string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    stack<int> s;
    for(int i = 0; i < n; i++){
        ss.insert(i);
    }
    
    set<int> :: iterator it,temp;
    it = ss.begin();
    
    //초기 위치 값 설정
    while(k--){
        it++;
    }

   for(int i =0; i < cmd.size(); i++){
       string str = cmd[i];

       //c cmd 수행
       if(str == "C"){// 삭제
           s.push(*it); // 원소 값
           temp = it;
           temp++;
           if(temp == ss.end()){ // 마지막
               temp = it;
               --temp;
           }
           ss.erase(it);
           it = temp;
        //z cmd 수행
       }else if(str == "Z"){
          ss.insert(s.top());
           s.pop();
       }else{
           if(str[0] == 'D'){
               string ss = str.substr(2);
                int val = stoi(ss);
               while(val--){
                   ++it;
               }
           }else if(str[0] == 'U'){
               string ss = str.substr(2);
                int val = stoi(ss);
               while(val--){
                   --it;
               }
           }
    }

   }
    
    int idx=0;
    for(it = ss.begin(); it!=ss.end();it++){
        int val = *it;
        if(val==idx){
            answer+='O';
        } 
        else{
            while(idx<val){
                answer+='X';
                idx++;
            }
            answer+='O';
        }
        idx++;
    }
    while(idx<n){		//"OOOXX" 같은 예외 잡아주기 위함
        answer+='X';
        idx++;
    }

    return answer;
}