문제
핵심
- 입력의 크기가 1,000,000이라 대략 이하 알고리즘을 사용한다.
- 임의의 위치에서 삽입과 삭제가 반복된다. 직관적으로 list를 사용하는 문제임을 알 수 있다. 배열로 푸는 경우 임의의 위치에서 삭제하고 삽입하는 과정에서 배열 복사 비용이 들고, 효율성 케이스를 통과하지 못한다.
1. List STL
- C++에서 list 자료구조를 이용할 수 있을까? 사용할 수 있다. 하지만, 원소의 위치를 파악하기가 어렵다. 7번째 위치에 원소를 삽입해야 한다면, 해당 위치까지 iterator를 이동시켜야 한다. 이 작업은 O(N)으로 N이 1,000,000이고 명령어가 200,000까지 가능하기 때문에 효율성 케이스를 통과하지 못한다. 즉, 특정 위치의 원소에 바로 접근할 수 있는 iterator를 미리 준비해 두어야 한다. 아래처럼 iterator를 특정 인덱스마다 기록해 두면 에 접근할 수 있다. (즉, 삽입과 삭제가 가능하다)
auto it = l.begin();
for(int i = 0; i < n; i++){
l_it[i] = it;
it++;
}- 원소를 삭제할 때 삭제한 원소와 원소의 위치를 stack에 저장해두면 가장 최근에 삭제된 행을 에 찾을 수 있다. 삭제한 원소를 insert() 함수로 추가할 때 iterator 앞에 추가되는 것을 유의한다. 따라서 현재 커서에 있는 원소를 삭제할 때 커서 오른쪽 원소의 위치를 기억해 둔다. 그럼, 제일 마지막 원소를 삭제할 때 커서를 어디에 위치시켜야 할까? 그림에 나와 있듯 커서 왼쪽에 위치시킨다. 그림으로 나타내면 아래와 같다.
- 커서의 위치가 작아지면 제일 마지막 원소를 삭제한 것이고, 커지면 마지막 원소가 아닌 것을 삭제한 것이다. 다시 추가한 원소의 위치로 바로 접근할 수 있도록 iterator 위치를 추가하는 작업을 한다. 여기서 iterator를 직접 수정하게 되면 추후 iterator 연산 과정에서 예기치 못한 문제가 발생할 수 있으니 주의하자.
if (cur < nxt) {
l.insert(l_it[nxt], cur);
auto tmp = l_it[nxt];
tmp--;
l_it[cur] = tmp;
}
else {
l.insert(l.end(), cur);
l_it[cur] = --l.end();
}C++
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <iterator>
#include <list>
using namespace std;
list<int> l;
list<int>::iterator l_it[1000004];
list<int>::iterator cursor;
stack<pair<int,int>> s;
string solution(int n, int k, vector<string> cmd) {
for(int i = 0; i < n; i++)
l.push_back(i);
auto it = l.begin();
for(int i = 0; i < n; i++) {
l_it[i] = it;
it++;
}
cursor = l_it[k];
for (auto str : cmd) {
if (str[0] == 'U') {
int num = stoi(str.substr(2));
while(num--) --cursor;
}
else if (str[0] == 'D') {
int num = stoi(str.substr(2));
while(num--) ++cursor;
}
else if (str[0] == 'C') {
auto init = cursor;
cursor = l.erase(cursor);
if (cursor == l.end()) {
--cursor;
}
s.push({ *init, *cursor });
}
else {
auto [cur, nxt] = s.top(); s.pop();
if (cur < nxt) {
l.insert(l_it[nxt], cur);
auto tmp = l_it[nxt];
tmp--;
l_it[cur] = tmp;
}
else {
l.insert(l.end(), cur);
l_it[cur] = --l.end();
}
}
}
string str(n, 'X');
for (auto e : l) {
str[e] = 'O';
}
return str;
}
개선
- 가장 끝에 더미 원소를 추가해 해당 분기 처리를 간단하게 할 수 있다.
string solution(int n, int k, vector<string> cmd) {
for(int i = 0; i < n + 1; i++)
l.push_back(i);
auto it = l.begin();
for(int i = 0; i < n + 1; i++){
l_it[i] = it;
it++;
}
...
for (auto str : cmd) {
...
else if (str[0] == 'C'){
s.push({*cursor, *(next(cursor))});
cursor = l.erase(cursor);
if (*cursor == n) --cursor;
}
else {
auto [cur, nxt] = s.top(); s.pop();
l_it[cur] = l.insert(l_it[nxt], cur);
}
}
...Java에도 LinkedList()가 존재한다. 구현이 가능할까?
- 이론상은 구현 가능하다. 하지만, 직접 해본 결과 iterator를 사용하는 데 있어서 제한이 많았고, 특히 동시 수정 문제가 엄격하다.
2. 직접 List 구현
1. C++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MX = 1'200'004;
int dat[MX];
int pre[MX];
int nxt[MX];
int nums[MX];
int unused = 1;
int insert(int addr, int num) {
dat[unused] = num;
pre[unused] = addr;
nxt[unused] = nxt[addr];
if (nxt[addr] != -1) pre[nxt[addr]] = unused;
nxt[addr] = unused;
return unused++;
}
int erase(int addr){
nxt[pre[addr]] = nxt[addr];
if (nxt[addr] != -1) {
pre[nxt[addr]] = pre[addr];
return nxt[addr];
}
return pre[addr];
}
string solution(int n, int k, vector<string> cmd) {
dat[0] = nxt[0] = -1;
for (int i = 0; i < n; ++i)
nums[i] = insert(i, i);
int cursor = nums[k];
stack<pair<int, int>> s;
for (auto str : cmd) {
if (str[0] == 'U'){
int num = stoi(str.substr(2));
while(num--) cursor = pre[cursor];
}
else if (str[0] == 'D'){
int num = stoi(str.substr(2));
while(num--) cursor = nxt[cursor];
}
else if (str[0] == 'C'){
s.push({ dat[pre[cursor]], dat[cursor] });
cursor = erase(cursor);
}
else {
auto [cur, nxt] = s.top(); s.pop();
int idx;
if (cur == -1) idx = 0;
else idx = nums[cur];
nums[nxt] = insert(idx, nxt);
}
}
string str(n, 'X');
int cur = nxt[0];
while (cur != -1) {
str[dat[cur]] = 'O';
cur = nxt[cur];
}
return str;
}2. Java
import java.util.*;
public class Solution {
final int MX = 1200004;
int[] dat = new int[MX];
int[] pre = new int[MX];
int[] nxt = new int[MX];
int[] nums = new int[MX];
int unused = 1;
public int insert(int addr, int num) {
dat[unused] = num;
pre[unused] = addr;
nxt[unused] = nxt[addr];
if (nxt[addr] != -1) pre[nxt[addr]] = unused;
nxt[addr] = unused;
return unused++;
}
public int erase(int addr) {
nxt[pre[addr]] = nxt[addr];
if (nxt[addr] != -1) {
pre[nxt[addr]] = pre[addr];
return nxt[addr];
}
return pre[addr];
}
public String solution(int n, int k, String[] cmd) {
dat[0] = nxt[0] = -1;
for (int i = 0; i < n; i++)
nums[i] = insert(i, i);
int cursor = nums[k];
Stack<int[]> s = new Stack<>();
for (String str : cmd) {
if (str.charAt(0) == 'U') {
int num = Integer.parseInt(str.substring(2));
while (num-- > 0) cursor = pre[cursor];
} else if (str.charAt(0) == 'D') {
int num = Integer.parseInt(str.substring(2));
while (num-- > 0) cursor = nxt[cursor];
} else if (str.charAt(0) == 'C') {
s.push(new int[] { dat[pre[cursor]], dat[cursor] });
cursor = erase(cursor);
} else {
int[] top = s.pop();
int cur = top[0];
int next = top[1];
int idx;
if (cur == -1) idx = 0;
else idx = nums[cur];
nums[next] = insert(idx, next);
}
}
StringBuilder str = new StringBuilder("X".repeat(n));
int cur = nxt[0];
while (cur != -1) {
str.setCharAt(dat[cur], 'O');
cur = nxt[cur];
}
return str.toString();
}
}
꾸준하게