코딩테스트 -- 표 편집- (프로그래머스 / C++)

코딩테스트 연습 - 표 편집

문제 설명

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

---

요약하면 명령어에 따라 행을 이동하며 삭제, 복구, 이동을 해보는 문제입니다!

 

바로드는 생각으로는 실제로 행을 지우기보단 지웠다고 표시해주는 방법이 좀더 빠를거 같네요!

(만약 실제로 삭제하면 나중에 복구할때 위치도 알아야하고 그사이에 넣어야하는게.... 좀 걸릴꺼 같아요)

 

그래서! 바로 구현해보았습니다.... 실패..

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int cal_index(vector<string> answer_mem,int now,int add){
    int answer=0;
    int count=0;
    
    if(add > 0){//내려가기
        for(int i=now+1;i<answer_mem.size();i++){
            if(answer_mem[i]=="O"){
                count+=1;
            }
            if(add==count){
                answer=i;
                break;
            } 

        }
    }
    else{//올라가기
        for(int i=now-1;i>=0;i--){
            
            if(answer_mem[i]=="O"){
                count+=1;
            }
            
            if(add*(-1)==count){
                answer=i;
                break;
            } 
        }
    }
    
    return answer;
}

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    
    int now_in=k;
    int memo=0;
    vector<int> c_index;
    vector<string> answer_mem(n);
    
    
    for(int i=0;i<n;i++){//초기화
        answer_mem[i]="O";
    }
    
    
    for(string i : cmd){
        if(i[0]=='D'){
            now_in=cal_index(answer_mem,now_in,int(i[2]-'0'));
        }
        else if(i[0]=='U'){
            now_in=cal_index(answer_mem,now_in,(-1)*int(i[2]-'0'));
        }
        else if(i[0]=='C'){//삭제
            answer_mem[now_in]="X";
            c_index.push_back(now_in);
            if(now_in==n-1){
                now_in=cal_index(answer_mem,now_in,-1);
            }
            else{
                now_in+=1;
            }
            
        }
        else{//뒤로가기 Z
            memo=c_index.back(); //불러올 인덱스
            c_index.pop_back();
            answer_mem[memo]="O";

        }
        
    }
    
    for(string i : answer_mem){
        answer+=i;
    }
    
    
    return answer;
}

어디서 틀렸는지 감이 안오네요...  약간 쎄한부분이 cal_index()함수에서 이동할때 무언가 잘못이동하는거 같은데...

 

 

실패 뿐만아니라 시간초과까지...!! 

시간초과나는건 아마 지워진 부분도 이동할때 탐색을 하게되면서 엄청난 숫자가 나오나보네요..

 

지우고 다시 집어넣는 부분이 오래 걸릴꺼 같아서 다른방법을 써 보았는데 이게 더 느리네요 ㅋㅋㅋ

 

다른방법으로 ㄱㄱ!

 

결국 서칭해봤습니다.... 이 문제는 대부분 연결리스트로 풀어 놓으셨더라구요

 

앞부분과 뒷부분을 이어 삭제되어도 이동되게 삽입할때도 중간부분에 넣어주고... 

연결리스트를 이런데 적용할수있는지는 생각도 못했네요 ㅠ

 

한번해보죠!

 

먼저 벡터들을 선언해주고 

    vector<int> mem_index;//삭제된 인덱스 저장
    vector<int> prev;//앞에 연결되어있는거
    vector<int> next;//뒤에 연결되어있는거

    for (int i = 0; i < n + 2; i++) {//i의 앞과 뒤 인덱스 저장
        prev.push_back(i - 1);
        next.push_back(i + 1);
    }
    
    k++; // 인덱스를 1~n까지 할것!

각각 어디에 연결되어있는지 확인해줍시다!

 

여기서 k를 한칸 올려줍시다.

(현재 위에서 0인덱스에는 -1과 1이 연결되어버리기에 1부터 n까지쓰고 나중에 -1 하기!)

 

 

이제 명령어 수행부분

for (int i = 0; i < cmd.size(); i++) {
        if (cmd[i][0] == 'U') {//올라가기
            for (int j = 0; j < stoi(cmd[i].substr(2)); j++) {
                k = prev[k];
            }
        }
        else if (cmd[i][0] == 'D') {//내려가기
            for (int j = 0; j < stoi(cmd[i].substr(2)); j++) {
                k = next[k];
            }
        }
        else if (cmd[i][0] == 'C') {//삭제
            mem_index.push_back(k);
            next[prev[k]] = next[k];//새로이어주기
            prev[next[k]] = prev[k];

            if (next[k] == n + 1){
                k = prev[k];
            } 
            else{
                k = next[k];
            } 
        }
        else if (cmd[i][0] == 'Z') {//되돌리기
            int r = mem_index.back();
            next[prev[r]] = r;
            prev[next[r]] = r;//이어주기
            mem_index.pop_back();
        }
    }

 

이동할때는

for (int j = 0; j < stoi(cmd[i].substr(2)); j++) {
                k = prev[k];
            }

 이렇게 k를통해 계속 반복되며 이동해주고

 

 

삭제나 삽입에서는

next[prev[k]] = next[k];
prev[next[k]] = prev[k];

앞뒤자리의 배열에 이어주는값을 변경하여 다르게 이어줍시다.

 

 

 

다 수행하고 나서 여전히 삭제된 부분은 'x'로 출력해주면 끝!

    string answer;
    answer.append(n, 'O');

    
    while (mem_index.size()!=0) {
        answer[mem_index.back() - 1] = 'X';
        mem_index.pop_back();
    }

 

다 풀고 나니까 2번째 방법도 실제로 삭제하는것 보다는 이어짐을 끊어주는 방법이네요!

 

첫번째방법도 참신하다고 생각했는데 조금 더 나갔어야했네요... 분발하겠습니다!

 

 

 

 

틀린 점이 있다면 댓 달아주세요!