pushback

 사연이 많은 문제다. 자세한 사연은 아래 코드 밑에 달아놓겠다.

 list 자료구조를 이용하여 해결하는 문제다. 간단해 보이지만 시간초과(TLE)를 피하기 위해 몇 가지 노력이 필요하다.

 첫번째, U와 D의 경우 매번 위아래로 움직이지말고 움직여야하는 횟수를 기록하자. 예를 들어, "U 10, D 12" 가 나왔다고 가정해보자.

매번 움직이게되면 22번의 움직임이 필요하지만, "U 10"일 때 -10, "D 12"일때 +12 를 해서 결국 -10+12  = 2을 구하여 아래로 두번만 움직이면 되는 극강의 가성비를 보여준다. 

 두번째, C와 Z를 처리할 때 상수 시간에 처리할 수 있는 방법을 생각해보자. 이게 왜 필요하냐면, list는 인덱스 접근이 불가하다.

또  이게 왜 문제가 되냐면, 선택된 행이 0일 때 "C, D 10000, Z" 가 입력이 되었다고 가정해보자.

현재 행을 지우고, 아래로 10000만큼 움직이고 Z가 입력이 들어오면,  다시 위로 10000만큼 움직여서 전에 삭제되었던 숫자를 삽입한다.

이렇게 구현하면 TLE에 걸릴게 뻔하기 때문에 C와 Z는 \(O(n)\)보단 작아야 한다.

그래서 나는 list iterator 1,000,001개를 FLEX했다. 용도는 list 원소에 \(O(1)\)에 접근하기 위해서이다. 

 세번째, Z를 처리할 때 복구해야할 게 뭔지 \(O(1)\)에 알아야 한다. 가장 적합한 자료구조가 하나 떠오른다. 바로 스택이다. 스택과 함께라면 Z를 처리하는 것은 문제가 없어 보인다.

 이제 정확히 어떻게 처리하는지 알아보자.

 초기 설정으로 \(0\) ~ \(n-1\)을 원소로 갖는 list와 그 원소들을 가르키는 \(n\)개의 iterator를 준비하자.

 우선 U와 D는 앞서 언급한 대로 하면 충분히 시간을 줄일 수 있을 것으로 보인다.

 C가 입력으로 들어오면 우선 현재 선택된 행을 업데이트하고, 선택된 행을 지워준 후 문제에서 제시한대로 다음 행을 선택해준다. 마지막으로 지워진 행의 숫자와 다음 선택된 행의 숫자를 스택에 넣어준다.

 Z가 입력으로 들어오면 가장 최근에 삭제된 숫자가 뭔지 알기 위해 스택의 top을 갖고오자. 현재 우리는 가장 마지막에 지워진 숫자(cur)와 그 숫자가 지워지고 선택된 행의 숫자(next)를 알고 있다. 응? 그래서 뭐...?

 자, 다시 cur이 지워졌을 때를 다시 생각해보자. 

 ...- prev - cur - next -... 이었던 상황에서, cur이 삭제되면

 ...- prev - next - ... 이 되었을 것이다. 여기서 우리는 다시 cur을 제자리에 넣어야 한다.

 어떻게 ???

 list container를 사용하고 있기 때문에 insert만 사용해주면 된다. 

 왜????

 list의 insert는 파라미터로 iterator와 삽입할 값을 넘겨주면, 해당 iterator 앞에 그 값을 삽입해준다. 무슨 말이냐?

 ...- prev - next -... 에서 list.insert(next를 가르키는 iterator, cur)을 해주면

 ...- prev - cur - next -... 이 된다.

정확히 말하면 넘겨받은 iterator자리에 값이 삽입되는건데, 결과적으로 보면 넘겨받은 iterator 앞에 넣어주는 것처럼 보인다. 

그러면 삽입이 끝났으니까 원래 상태로 돌아왔으니까 끝? 당연히 아니다.

cur을 가르키던 iterator는 아직 삭제된 cur을 가르키고 있다. 우리는 cur을 다시 삽입했으니까, 새로 생긴 cur을 가르키게 해야된다.

휴, 이제 다 끝났네.. 아직 하나 더 남았다.

만약 cur이 마지막 원소였다면...? next는 위치상으로 cur의 이전 원소가 된다.

따라서 만약 next가 cur보다 작은 값이라면, cur은 list의 마지막 원소였기 때문에 next의 자리에 insert가 아니라 list의 마지막 자리에 insert를 해야 복구가 완성된다.(이거 안해주면 대참사난다.)

 자 다왔다.. 결과적으로 Z를 처리하기 위해서

1. 스택의 top을 보자.
2. 지워진 숫자(cur)와 다음으로 선택된 숫자(next)의 관계를 보자.
3. cur < next라면, next자리에 insert
4. cur > next라면, list.end()에 insert
5. 새로 생긴 cur을 cur을 가르키는 iterator에 업데이트

의 과정이 필요하다. 

 끝났다. 이제 구현하자.

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <iterator>
#include <list>

using namespace std;

bool isRemoved[1000001] = { 0, }; // 삭제된 숫자 확인
list<int>::iterator l_it[1000001]; // 인덱스에 해당하는 숫자를 가르키는 iterator들
list<int> li;
list<int>::iterator cur; // 현재 선택된 행

stack<pair<int, int>> stk;
int tmp = 0;

void move() { 
// tmp에 저장되어있는 숫자만큼 움직여준다 == 선택된 행 업데이트
    if (tmp > 0) while (tmp--) { cur++; }
    else if (tmp < 0) while (tmp++) { cur--; }

    tmp = 0;
}

void U(int x) {
    tmp -= x;
}

void D(int x) {
    tmp += x;
}

void C() {
    // 선택된 행 업데이트
    move();
    // 지워질 행을 미리 저장
    list<int>::iterator er = cur;
    // 지워질 숫자를 미리 저장
    int erase_num = *er;
    cur++; // cur은 다음 원소를 가르킨다.

    li.erase(er); 

    if (cur == li.end()) --cur; // 다음 원소가 list의 end()라면 이전 원소를 가르킨다
                                // 이 부분은 list에 대한 이해가 필요
	
    // 지워진 숫자 체크
    isRemoved[erase_num] = true;
    // 지워진 숫자와 지워진 다음 선택된 숫자 스택에 push
    stk.push({ erase_num, *cur });
}

void Z() {
	// 선택된 행 업데이트
    move();
	// 지워진 숫자와 다음 선택된 숫자
    int erase_num = stk.top().first;
    int next = stk.top().second;
    stk.pop();
	
    // 지워진 숫자가 list의 가장 마지막이 아니었을 때
    if (erase_num < next) {
        // erase_num - next 가 되었다.    
        li.insert(l_it[next], erase_num);
        // erase_num의 iterator 업데이트
        auto tmp = l_it[next];
        tmp--;
        l_it[erase_num] = tmp;
    }
    // 지워진 숫자가 list의 가장 마지막이었을 때
    else {
        li.insert(li.end(), erase_num);
        l_it[erase_num] = --li.end();
    }
    // 다시 돌아왔으니 체크 해제
    isRemoved[erase_num] = false;
}


string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    // init
    li.resize(n);
    int i = 0;
    for (auto it = li.begin(); it != li.end(); ++it, ++i) {
        *it = i;
        l_it[i] = it;
    }

    cur = l_it[k];


    for (int i = 0; i < cmd.size(); ++i) {
        char ch = cmd[i][0];
        if (ch == 'U' || ch == 'D') {
            int x = 0;
            for (int j = 2; j < cmd[i].size(); ++j) x = x * 10 + (cmd[i][j] - '0');

            if (ch == 'U') U(x);
            else D(x);
        }
        else if (ch == 'C') C();
        else if (ch == 'Z') Z();
    }

    for (int i = 0; i < n; ++i) {
        if (isRemoved[i]) answer += 'X';
        else answer += 'O';
    }

    return answer;
}

비하인드 스토리

 우선, 문제를 읽자마자 삽입 삭제에 유리한 컨테이너가 필요함을 알았다. 여기서 한가지 바보 moment가 발생하는데, 이제까지 나는 deque의 삽입, 삭제가 \(O(1)\)인 줄 알았다. deque라는 것 자체가 굉장히 자유분방(?)해보여서 insert도 \(O(1)\)일 것이라고 오해를 했다. 결국 deque로 구현한 코드는 당연히 TLE를 나에게 선사해주었고, 이해가 안된 나는 C++ reference를 뒤져보았고, 그 곳에 떡하니 time complexity가 linear time 이라고 적혀있는 것을 보았다. deque는 vector기반이라 당연한 것이었다. 일단 여기까지 대략 한시간이 증발했다. 

 정신을 부여잡고 삽입 삭제에 유리한 다음 타자로 list를 선택했다. 근데 문제가 있다. 인덱스 접근이 불가능하다. 당연히 doubly linked list로 구현이 되어있으니까 불가능하다. 그럼 또 당연히 TLE를 피하는 것도 불가능하다. (이 때는 위에 풀이와 같이 iterator를 1,000,001개 선언할 생각을 못했다.) 이렇게 30분정도가 또 지나버렸다.

 입에 욕을 머금고 생각을 해보니 삽입 삭제에 유리한 다음 타자 세그먼트 트리가 떠올랐다. 이거면 무조건 된다고 생각했다. 시간 복잡도가 세그먼트 트리로 구현하면 \(O(n(log n)^2 )\)이기 때문에 충분해 보였다. 결과는 효율성에서 몇개였는지 기억은 안나는데 2~3개정도가 시간초과가 나왔다. 좀 더 생각해보다가 시간을 줄일 수 있는 부분이 없다는 판단을 내렸다. 이렇게 또 다른 30분이 지났다.

 다른 사람들이 문제 풀이에 대해 질문한 것을 봤다. 누군가가 세그먼트 트리를 비재귀로 구현하면 통과가 된다고 한다. 세그먼트 트리 비재귀 검색해서 찬찬히 살펴봤다. 비재귀를 이용해서 구현해봤다. 제출해보니 여기저기서 WA가 뜬다. 이상하다. 재귀 세그먼트 트리랑 비재귀 세그먼트 트리랑 만들어지는 트리가 뭔가 다르다. 이 부분을 이해하면 됐을 것 같은데 힘이 없어서 포기했다. 또 한시간이 지났다.

 가만히 비재귀 세그먼트 트리 코드를 보고있으니.. 이거 펜 윅 트리랑 비슷하게 생겼다. 근데 나는 펜 윅 트리를 공부해본 적이 없다. 그래서 또 펜 윅 트리를 검색해서 찬찬히 살펴봤다. 내가 이해한 것을 토대로 구현해봤다. 또 WA가 보인다. 아무래도 비재귀 세그먼트 트리나 펜 윅 트리나 내가 제대로 이해하지 못한 부분이 있어보였다. 이렇게 두시간이 더 흘렀다. 나는 더 참지 못하고 노트북을 덮었다.

 다음 날이 됐다. 다시 앉아서 list로 돌아왔다. 불현듯이, iterator가 배열로 선언이 되는지 궁금했다. 다른 ide에서 몇 가지 테스트를 해보니 이거 된다..! 이거면 list 원소들에 \(O(1)\)에 접근이 가능하다. 다시 list와 1,000,001개의 iterator를 등에 업고 구현을 시작했다. 이미 5~6시간을 꼬라박은 문제라 구현하는데 10분도 안걸렸다. 첫번째 시도 때 Z에서 선택된 행 업데이트를 깜빡하고 빼먹어서 WA를 받았다. 다시 디버깅을 하고 제출하고 맞아버렸다.

 아직도 비재귀 세그먼트 트리랑 펜 윅 트리를 이용한 풀이가 왜 안되는지 이해가 안된다. 혹시라도 세그먼트 트리를 이용해서 해결하신 분이 계시다면.. 제발 댓글로 힌트 좀 부탁드린다..

 구현 문제이다. 

 각 방의 모든 사람의 위치를 구하고, 모든 사람들의 서로 간의 거리를 확인하자.

 문제 조건대로 거리가 1이면 거리 두기 위반, 2이면 위반했는지 확인 필요, 3 이상이면 거리 두기이다.

 핵심은 거리가 2일 때 위반했는지 확인하는 것인데, 거리가 2인데 거리 두기를 유지하는 경우는 

1. P X P
2. P
   X
   P
3. P X
   X P
4. X P
   P X

 이렇게 4가지 경우 밖에 없다. 이것만 잘 확인해주면 쉽게 풀리는 문제다.

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <math.h>

using namespace std;

char room[5][5][5];
vector<pair<int, int>> person[5];
bool checkPartition(int, pair<int, int>&, pair<int, int>&);

// 거리 계산
int calDist(pair<int, int>& p1, pair<int, int>& p2) {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

// 각 대기실에 있는 사람들간의 거리 확인
bool checkDist(int cur) {
    if (person[cur].size() == 0) return true;
	// 지금 생각해보니 sorting이 필요없다.. 이미 sort되어있는 상태이기 때문
    sort(person[cur].begin(), person[cur].end());

    for (int i = 0; i < person[cur].size(); ++i) {
        for (int j = i + 1; j < person[cur].size(); ++j) {
            int dist = calDist(person[cur][i], person[cur][j]);
            // 거리가 1이면 거리두기 위반
            if (dist == 1) return false;
            // 거리가 2이면 거리두기 위반했는지 확인
            else if (dist == 2) {
                if (!checkPartition(cur, person[cur][i], person[cur][j]))
                    return false;
            }
        }
    }
    // 이중 for문을 빠져나왔다면 거리두기를 지킨 것이다.
    return true;
}

bool checkPartition(int cur_room, pair<int, int>& p1, pair<int, int>& p2) {
    // P X P
    if (p1.first == p2.first) {
        if (room[cur_room][p1.first][p1.second + 1] == 'X') return true;
    }
    // P
    // X
    // P
    else if (p1.second == p2.second) {
        if (room[cur_room][p1.first + 1][p1.second] == 'X') return true;
    }
    else {
        // P X 
        // X P  
        if (p1.second < p2.second) {
            if (room[cur_room][p1.first][p1.second + 1] == 'X'
                &&
                room[cur_room][p2.first][p2.second - 1] == 'X'
                )
                return true;
        }
        // X P
        // P X
        else {
            if (room[cur_room][p1.first][p1.second - 1] == 'X'
                &&
                room[cur_room][p2.first][p2.second + 1] == 'X'
                )
                return true;
        }
    }

    return false;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            for (int k = 0; k < 5; ++k) {
                room[i][j][k] = places[i][j][k];
                if (room[i][j][k] == 'P') person[i].push_back({ j, k });
            }
        }
    }
    for (int i = 0; i < 5; ++i) {
        if (checkDist(i)) answer.push_back(1);
        else answer.push_back(0);
    }

    return answer;
}

 간단한 구현 문제이다.

 좀 간단한 코드로 풀어보고 싶었는데 언어의 한계와 두뇌의 한계로 조건문 떡칠해서 해결했다.

 핵심은 영단어 앞에 한 개 혹은 두 개 알파벳만 확인하면 어떤 숫자로 치환해야할지 알 수 있다는 것이다.

 어떤 숫자로 치환해야 할 지 알았다면, (알파벳 수 - 1)만큼 jump해준다.

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    for (int i = 0; i < s.size(); ++i) {
        int next = 0;
        if (s[i] >= '0' && s[i] <= '9') next = (s[i] - '0');
        else {
            if (s[i] == 'z') next = 0, i += 3;
            else if (s[i] == 'o') next = 1, i += 2;
            else if (s[i] == 't') {
                if (s[i + 1] == 'w') next = 2, i += 2;
                else next = 3, i += 4;
            }
            else if (s[i] == 'f') {
                if (s[i + 1] == 'o') next = 4, i += 3;
                else next = 5, i += 3;
            }
            else if (s[i] == 's') {
                if (s[i + 1] == 'i') next = 6, i += 2;
                else next = 7, i += 4;
            }
            else if (s[i] == 'e') next = 8, i += 4;
            else if (s[i] == 'n') next = 9, i += 3;
        }
        answer = answer * 10 + next;
    }
    return answer;
}