2021 카카오 채용연계형 인턴십 ①

 

 

#3 표 편집

간단해 보이나 효율성을 통과하기 위해 배열 외의 자료구조를 선택해야 했음

set을 이용한 풀이도 가능하지만 fenwick tree로도 풀 수 있다해 풀어봤다.

 

은근히 이분탐색에서 헷갈렸던;; 어떤 L을 찾는지 명확히 해야 헷갈리지 않는다.

시험 볼 당시에는 set을 활용하려 했으나 iterator 활용을 잘 못해 실패했던 것 같다...

 

fenwick tree와 이분탐색을 이용함.

 

#include <string>
#include <vector>
#include <stack>
using namespace std;

int N;
stack<int> S;
int fen[1000001];
void upd(int idx, bool add) {
    if (add) while (idx <= N) fen[idx]++, idx += (idx & -idx);
    else while (idx <= N) fen[idx]--, idx += (idx & -idx);
}
int sum(int idx) {
    int ret = 0;
    while (idx) ret += fen[idx], idx -= (idx & -idx);
    return ret;
}
string solution(int n, int k, vector<string> cmd) {
    N = n; k++;
    for (int i = 1; i <= n; ++i) upd(i,true);

    bool up;
    int x = 0, qsize = 0, L, R, mid, goal;
    for (string q : cmd) {
        if (q[0] == 'Z') { upd(S.top(), true); S.pop(); continue; }

        if (q[0] == 'U') {
            qsize = q.size(); x = 0; up = true;
            for (int i = 2; i < qsize; ++i) x *= 10, x += (q[i] - '0');
        }
        else if (q[0] == 'D') {
            qsize = q.size(); x = 0; up = false;
            for (int i = 2; i < qsize; ++i) x *= 10, x += (q[i] - '0');
        }
        else if (q[0] == 'C') {
            upd(k, false); S.push(k);
            if (sum(n) - sum(k)) up = false, x = 1;
            else up = true, x = 0;
        }

        if (up) goal = sum(k) - x,  L = 1, R = k - 1;
        else goal = sum(k) + x, L = k + 1, R = n; 
        
        while (L < R) { //sum(mid)=goal인 mid의 최솟값을 구한다.
            mid = (L + R) >> 1;
            if (sum(mid) < goal) L = mid + 1;
            else R = mid;
        }
        k = L;
    }
    string ans(n, 'O');
    while (!S.empty()) ans[S.top() - 1] = 'X', S.pop();
    return ans;
}

 

각 행을 1~N이라고 생각하고 (문제에서는 0~N-1로 생각하기 때문)

i행이 존재하면 a[i]=1, 삭제되면 a[i]=0이 되도록 펜윅트리를 만든다.

즉 sum(i) = 1~i행 사이에 존재하는 행의 개수

쿼리를 수행하기 전에 1~N에 대해 펜윅트리를 +1만큼 업데이트한다. line 19~20

 

Z 가장 최근에 삭제한 행을 복구한다. 삭제한 행의 번호를 스택에 넣어둔 뒤 빼주면 됨 line 25

U/D X 움직일 행의 개수 x를 구하고 움직이는 방향을 up에 업데이트한다. line 27~34

C 현재 행인 k행을 삭제함을 펜윅트리 상에서 업데이트하고 스택에 넣는다.

k행이 마지막행이면 방향은 위, x=0으로, 아니면 방향은 아래, x=1로 업데이트한다. line 35~39

 

현재 k행에서 움직인 후의 행을 찾기 위해 위/아래 방향에 따라 goal을 설정한다. line 41~42

펜윅트리의 sum함수와 이분탐색을 이용해 다음 k인 L을 찾아 k를 업데이트한다. line 44~49

다음 k

= sum(i)=goal을 만족하는 i 중 최솟값

= k가 위/아래로 x만큼 움직인 후의 행 번호 

 

쿼리 수행을 종료하면 길이 n의 문자열 모든 문자를 'O'로 초기화한 뒤 스택을 이용해 삭제된 행에 대해서만 문자를 X로 바꾼다. line 51~53