명령어를 여러번 시행하여 나오는 결과를 출력하는 문제이다.
카카오 코딩테스트로 시험 당시에는 풀지 못했던 문제이다.
문제 해결 전략
0부터 n까지 저장한 자료구조와 삭제한 것들을 저장한 자료구조 두개를 선언한다.
예를들어 0 1 2 3 4 5 6 이 있을 때 3을 제거하는 상황을 보자.
원본은 0 1 2 4 5 6 이 될 것이고 삭제한 것을 저장한 것은 3이 될 것이다.
이 상태에서 위아래로 움직인 후 5를 제거하게 된다면
원본은 0 1 2 3 6 삭제한 것은 3 5 가 된다.
이 상황에서 복구를 하는 상황이라면 가장 최근의 것을 복구하기 때문에 5가 복구 될 것이다.
한번 복구를 하면 원본은 0 1 2 3 5 6 삭제는 3이 된다.
이런식으로 두개의 자료구조를 이용하여 생각해 볼 수 있다.
패배 요인
코딩테스트 당시에는 두 자료구조를 모두 벡터를 사용하였다.
벡터는 중간 삽입과 중간 삭제를 제공하기 때문에 벡터를 사용하였다.
하지만 벡터는 연속된 구조를 갖기 때문에 삽입, 삭제 시 O(n)의 시간복잡도를 갖게 되고, 이 과정이 충분히 많이 일어나야 하기 때문에 시간초과가 거렸었다.
해결 과정
set 자료구조는 중간 삽입, 삭제를 제공하며 트리 형태로 저장되기 때문에 삽입, 삭제의 시간복잡도는 O(logn)을 갖는다.
따라서 벡터 대신 set을 사용하면 시간내에 충분히 문제를 해결할 수 있다.
팁
- substr()
나는 함수를 만들어서 문자열을 숫자로 변환하도록 하였는데, substr을 사용하면 좀 더 짧고 간편하게 수행할 수 있다. - set의 erase()함수
erase를 시행하게 되면 지운 반복자의 다음 반복자를 가리키게 된다. 이것을 활용하여 문제의 조건 중 '삭제 시 다음을 가리킴'을 좀 더 쉽게 다룰 수 있었다.
코드
#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int toInt(string str){
string tmp = "";
for(int i=2;i<str.size();i++)
tmp += str[i];
return stoi(tmp);
}
string solution(int n, int k, vector<string> cmd) {
string answer = "";
for(int i=0;i<n;i++)
answer += 'X';
set<int> s;
vector<int> d;
for(int i=0;i<n;i++){
s.insert(i);
}
auto iter = s.begin();
for(int i=0;i<k;i++){
iter++;
}
for(int i=0;i<cmd.size();i++){
char c = cmd[i][0];
if(c == 'U'){
int x = toInt(cmd[i]);
for(int j=0;j<x;j++){
iter--;
}
}else if(c == 'D'){
int x = toInt(cmd[i]);
for(int j=0;j<x;j++){
iter++;
}
}else if(c == 'C'){
d.push_back(*iter);
iter = s.erase(iter);
if(iter == s.end())
iter--;
}else if(c == 'Z'){
int tmp = d[d.size()-1];
d.pop_back();
s.insert(tmp);
}
}
for(auto it = s.begin();it!=s.end();it++){
answer[*it] = 'O';
}
return answer;
}더 생각해 볼 점
중간 부분에 삽입, 삭제를 한다는 점에서 연결리스트를 생각했었다. 연결리스트에서 접근은 힘들지만 삽입, 삭제는 O(1)로 해결할 수 있기 때문이다.
연결리스트 구현 참고 : https://yjyoon-dev.github.io/kakao/2021/07/24/kakao-tableedit/
출처 : https://programmers.co.kr/learn/courses/30/lessons/81303
