[2021 카카오 채용형 인턴십] 표 편집 (lv 3)

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

코딩테스트 연습 - 표 편집

이 문제를 딱 봤을 떄 생각나는 것은 링크드리스트와 스택을 사용하면 되겠다! 였습니다.

하지만 링크드리스트를 사용해본지... 오억년... 나는 까먹은지 오래..;;

고로, 다른 방법을 써보자 해서 잔머리를 쓴게 각 캐릭터들의 상태값을 저장하는 배열을 정의하여 사용하자! 라고 결정했고

그 결과 정확성 테스트는 통과했지만 효율성 테스트는 통과하지 못했습니다.

int. -> long long 으로 또 다시 잔머리를 써봤지만 역시나 소용이 없었고요...ㅎ

아래에서 링크드리스트를 사용한 풀이도 나와 있으니 저와 같은 실수를 하는 분들이 참고하시면 좋을 듯 합니다!

이 기회에 링크드리스트 다시 공부해보자구요! :)

 

[제한사항]

[초기 풀이법]

정확성 테스트는 통과하지만 효율성에서는 통과하지 못했습니다.

1. 각 캐릭터들의 상태를 저장하는 배열을 사용한다.

true면 남아있는 거고 false면 버려진 거라고 간주했습니다. (문제를 보니 대소관계? 순서는 바뀌지 않는걸 확인할수 있었습니다.) 그렇기때문에 이 방법을 사용할 수 있다고 생각했습니다.

2. 각 명령어를 받아서 명령어에 해당하는 함수를 사용해주면 된다.

#include <string>
#include <stack>
#include <sstream>

using namespace std;

bool check[200010];
stack <long long> trash;
long long cur;
long long n;

void go_down(long long dist) {

    while(dist) {
        cur++;
        if(cur >= n)
            cur = 0;
        if(check[cur] == true) {
            dist--;
        }
    }
    
}

void go_up(long long dist) {
    
    while(dist) {
        cur--;
        if(cur < 0)
            cur = n-1;
        if(check[cur] == true) {
            dist--;
        }
    }
}

void remove() {
    // 현재블록 죽임
    if(check[cur] == true) {
        check[cur] = false;
        trash.push(cur);
    }
        
    bool exist = false;
    // 아래 블록이 존재하는 지 확인
    for(long long i=cur+1; i<n; i++) {
        // 존재한다면 커서 거기로 이동
        if(check[i] == true) {
            cur = i;
            exist = true;
            break;
        }
    }
    // 마지막 원소일 경우
    if(exist == false) {
        // 그 위에 있는 원소를 커서로 선택
        for(long long i=cur-1; i>=0; i--) {
            if(check[i] == true) {
                cur = i;
                break;
            }
        }
    }
    
}


string solution(int N, int k, vector<string> cmd) {
    string answer = "";

    for(long long i=0; i<N; i++)
        check[i] = true;
    
    cur = k;
    n = N;
    
    for(auto c: cmd) {
        if(c == "C") {
            remove();
        }
        else if(c == "Z") {
            int recover_idx = trash.top(); trash.pop();
            check[recover_idx] = true;
        }
        else {
            string s[2];
            istringstream stt(c);
            stt >> s[0] >> s[1];
            
            if(s[0] == "D") {
                go_down(stoi(s[1]));
            }
            else if(s[0] == "U") {
                go_up(stoi(s[1]));
            }
        }
    }
        
    for(long long i=0; i<n; i++) {
        if(check[i] == true) {
            answer += "O";
        }
        else
            answer += "X";
    }
    return answer;
}

 

[다른 사람 참고 코드]

 

링크드리스트를 직접 구현

struct Node {
    int num;
    Node * prev;
    Node * next;
    Node (int num) : num(num), prev(NULL), next(NULL) {}; // 생성자
};

// 연결리스트 생성 및 연결
v = vector <Node*> (n);

for(int i=0; i<n; i++)
    v[i] = new Node(i);

v[0]->next = v[1];
v[n-1]->prev = v[n-2];

for(int i=1; i<n-1; i++) {
    v[i]->next = v[i+1];
    v[i]->prev = v[i-1];
}

원소 삭제

 // cur 위치의 원소를 지운다
 
 // 앞에 원소가 존재한다면
 if(v[cur]->prev != NULL)
    v[cur]->prev->next = v[cur]->next; // 앞 원소의 다음 커서를 현재 원소의 다음커서가 가르키는 노드를 가르키도록 한다.

// 뒤에 원소가 존재한다면
if(v[cur]->next != NULL) {
    v[cur]->next->prev = v[cur]->prev; // 뒤 원소의 앞 커서를 현재 원소의 앞커서가 가르키는 노드를 가르키도록 한다.
    cur = v[cur]->next->num; // 커서 또한 뒤에 있는 원소의 값으로 변경해준다.
}
// 맨 뒤라면 앞에 있던 원소로 값으로 커서 변경
else
    cur = v[cur]->prev->num;

삭제여부 확인

string answer(n, 'X');
// 삭제 여부 체크

answer[cur] = 'O';

// 링크드리스트를 타고 가면서 연결된 노드라면 O 로 바꿔준다.

// 현재커서 기준 왼쪽 체크 <-
while(v[leftCheck]->prev != NULL) {
    leftCheck = v[leftCheck]->prev->num;
    answer[leftCheck] = 'O';
}

// 오른쪽 체크 ->
while(v[rightCheck]->next != NULL) {
    rightCheck = v[rightCheck]->next->num;
    answer[rightCheck] = 'O';
}

 

[전체 코드]

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

using namespace std;

int cur;
stack <int> st;

struct Node {
    int num;
    Node * prev;
    Node * next;
    Node (int num) : num(num), prev(NULL), next(NULL) {};
};

vector <Node*> v;

void solve(vector <string> & cmd) {
    for(string s : cmd) {
        if(s[0] == 'D' || s[0] == 'U') {
            int x = stoi(s.substr(2));
            // down
            if(s[0] == 'D') 
                while(x--) 
                    cur = v[cur]->next->num;
            else
                while(x--)
                    cur = v[cur]->prev->num;
        }// delete
        else if(s[0] == 'C') {
            st.push(cur);
            if(v[cur]->prev != NULL)
                v[cur]->prev->next = v[cur]->next;
            if(v[cur]->next != NULL) {
                v[cur]->next->prev = v[cur]->prev;
                cur = v[cur]->next->num;
            }// 맨 뒤라면 앞에 있던 원소로 커서 변경
            else
                cur = v[cur]->prev->num;
        }// 최근에 삭제한 원소 원복
        else if(s[0] == 'Z') {
            int r = st.top(); st.pop();
            if(v[r]->prev != NULL)
                v[r]->prev->next = v[r];
            if(v[r]->next != NULL)
                v[r]->next->prev = v[r];
        }
        else return;
    }
}

string solution(int n, int k, vector<string> cmd) {
    string answer(n, 'X');
    
    // 연결리스트 생성 및 연결
    v = vector <Node*> (n);
    
    for(int i=0; i<n; i++)
        v[i] = new Node(i);
    
    v[0]->next = v[1];
    v[n-1]->prev = v[n-2];
    
    for(int i=1; i<n-1; i++) {
        v[i]->next = v[i+1];
        v[i]->prev = v[i-1];
    }
    
    // cmd 수행
    cur = k;
    solve(cmd);
    
    // 삭제 여부 체크
    int leftCheck = cur;
    int rightCheck = cur;
    
    answer[cur] = 'O';
    // 현재커서 기준 왼쪽 체크 <-
    while(v[leftCheck]->prev != NULL) {
        leftCheck = v[leftCheck]->prev->num;
        answer[leftCheck] = 'O';
    }
    
    // 오른쪽 체크 ->
    while(v[rightCheck]->next != NULL) {
        rightCheck = v[rightCheck]->next->num;
        answer[rightCheck] = 'O';
    }

    return answer;
}

 

이건 주말에 다시 풀어볼 예정입니다.