하루 하루는 성실하게
인생 전체는 되는대로

[프로그래머스] 표 편집

2 minute read

문제 설명

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

제한사항

  • 5 ≤ n ≤ 1,000,000
  • 0 ≤ k < n
  • 1 ≤ cmd의 원소 개수 ≤ 200,000
    • cmd의 각 원소는 “U X”, “D X”, “C”, “Z” 중 하나입니다.
    • X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
    • X가 나타내는 자연수에 ‘,’ 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
    • cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
    • 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
    • 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 “이름” 열을 사용하였으나, “이름”열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. “이름”열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
  • 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
  • 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) “Z”가 명령어로 주어지는 경우는 없습니다.
  • 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.

풀이

2시간 이상
처음에는 효율성 테스트를 고려하지 않고 일단 풀었다. 제한 시간이 있는 실제 테스트 환경에서는 효율성 테스트를 고민하는 것을 끝까지 고민할수는 없기에 일단 정확성이라도 통과하고자 vector를 이용한 풀이를 했다. vector의 erase, insert연산이 오래걸리는 탓인지 효율성 테스트는 통과하지 못 했었다.

링크드리스트를 이용한 풀이도 당연히 생각했었는데, 표의 처음과 끝을 계속해서 왕복하는 테스트케이스가 있을 경우 한 칸씩 이동하는 링크드리스트 구조도 효율적이지 않을거라 생각하여서 고민을 정말 많이하게 되었다.

// 처음과 끝을 왕복
{D 100000, C, Z, U 1000000, C, Z , D 1000000 ...}

결국 카카오의 해설을 참고하게 되었고, 링크드리스트로도 풀이가 가능하다는 문구를 보자마자 바로 구현했다.
이게 왜 되지? 라는 의문이 들었지만…..

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

역시 문제를 잘 읽자….. 아오…

코드

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

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    string ans(n , 'O');
    int idx = k, step;
    
    vector<int> stack;
    vector<int> prev(n);
    vector<int> next(n);
    
    for(int i =0; i < n; ++i){
        prev[i] = i - 1;
        next[i] = i + 1;
    }
    prev[0] = -1;
    next[n-1] = -1;
    
    for(string s : cmd){
        if(s[0] == 'D'){
            step = stoi(s.substr(2));
            while(step > 0){
                idx = next[idx];
                --step;
            }
        }
        else if(s[0] == 'U'){
            step = stoi(s.substr(2));
            while(step > 0){
                idx = prev[idx];
                --step;
            }
        }
        else if(s[0] == 'C'){
            ans[idx] = 'X';
            stack.push_back(idx);
            
            if(prev[idx] != -1) next[prev[idx]] = next[idx];
            if(next[idx] != -1) prev[next[idx]] = prev[idx];
            
            if(next[idx] == -1) idx = prev[idx];
            else idx = next[idx];
        }
        else if(s[0] == 'Z'){
            int zidx = stack[stack.size() - 1];
            stack.pop_back();
            ans[zidx] = 'O';
            
            if(prev[zidx] != -1) next[prev[zidx]] = zidx;
            if(next[zidx] != -1) prev[next[zidx]] = zidx;
        }
    }
    return ans;
}

이전 코드

// 09:50 ~ 
#include <string>
#include <vector>
#include <iostream>

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    string ans(n , 'O');
    int idx = k;
    
    // idx, val
    vector<pair<int,int>> stack;
    vector<int> v(n);
    for(int i =0; i<n; ++i) v[i] = i;
    
    for(string s : cmd){
        if(s[0] == 'D'){
            idx += stoi(s.substr(2));
        }
        else if(s[0] == 'U'){
            idx -= stoi(s.substr(2));
        }
        else if(s[0] == 'C'){
            ans[v[idx]] = 'X';
            stack.push_back({idx, v[idx]});
            
            v.erase(v.begin() + idx);
            if(idx == v.size()) --idx;
        }
        else if(s[0] == 'Z'){
            pair<int,int> p = stack[stack.size() - 1];
            stack.pop_back();
            ans[p.second] = 'O';
            
            v.insert(v.begin() + p.first, p.second);
            
            if(p.first <= idx) ++idx;
        }
    }
    return ans;
}

You may also enjoy