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

문제

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

코딩테스트 연습 - 표 편집

 

풀이

당시에 풀 때도 링크드리스트로 풀다가 삽질하고 set으로 방향을 틀었던 기억이 나는데 문제를 꼼꼼히 안읽으면 우왕좌왕 해매기 쉬운문제였던 것 같습니다. 다시 링크드리스트로 구현해봐야지,,

---

1. 주의 깊게 봐야하는 부분은 아래와 같습니다.

 

※ "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요. 

  → 결국 행 번호가 겹치지않는다는 의미입니다.

 

※ cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.

  → 현재 선택된 행에서 이동할 때 움직이는 부분을 어떻게 구현할지가 문제였는데 해당 조건을 보면 커서를 직접 움직여도 됩니다,,

 

 ※ 행을 삭제할 때, 커서가 맨 마지막 행이라면 바로 전 행으로 커서가 움직입니다.

  → 삭제시, 마지막 행인지 체크하고 직전 행으로 움직이도록 구현해야합니다.

 

  ※ X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.

  →  이 부분도 문제를 안읽고, 한참 해맸습니다,,

 

2. 중복없는 숫자들을 관리하며 위치를 움직인다 →  set을 이용하면 숫자 관리, iterator를 통한 커서관리를 할 수 있습니다.

    삭제된 숫자들을 복구한다 →  스택이나 벡터를 이용하여 마지막으로 들어온 행을 관리할 수 있고, 새로운 값이 추가되는 연산이 없기에 돌아 갈 위치는 유일합니다.

 

3. 따라서 앞서 언급한 내용을 종합하면 행 관리는 set을 이용하고, 삭제된 행관리는 벡터나 스택을 이용해 해결할 수 있습니다.

 

코드

1. Set을 이용한 풀이

#include <bits/stdc++.h>
using namespace std;

string solution(int n, int k, vector<string> cmd) {
    string answer ="";
    answer.resize(n, 'X');
    set<int> s;
    vector<int> del;
    for (int i = 0 ; i < n ; i++) s.insert(i);
    for (string c : cmd){
        if (c[0] == 'C') {
            int kk = k;
            set<int>::iterator cur = s.find(k);
            set<int>::iterator pre = prev(cur);
            set<int>::iterator nxt = next(cur);
            if (nxt == s.end()) k = *pre;
            else k = *nxt;
            del.push_back(kk);
            s.erase(kk);
        }
        else if (c[0] == 'Z') {
            s.insert(del.back());
            del.pop_back();
        }
        else if (c[0] == 'D' || c[0] == 'U'){
            int x = stoi(c.substr(2));
            set<int>::iterator cur = s.find(k);
            if (c[0] == 'D') while (x--) cur = next(cur);
            else while (x--) cur = prev(cur);
            k = *cur;
        }
    }
    for (int i : s) answer[i] = 'O';
    return answer;
}

 

2. 링크드리스트를 이용한 풀이(추후에,,)