2022 KAKAO TECH INTERNSHIP 행렬과 연산

성공 - 포인터 적용 필요 // (k % total) 효과는 크게 없었음 // 포인터 대신 top index 이용하여 shift() 처리할 수 있음

#include <string>
#include <vector>
#include <list>

using namespace std;
using vvi = vector<vector<int>>;

list<list<int>*> rows;
vector<list<int>> cols;
int N, M;

void shift(int k) {
    int total = rows.size();
    k = k % total;
    if (k == 0) return;

    for (int T = 0; T < k; ++T) {
        rows.push_front(rows.back());
        rows.pop_back();

        for (int i = 0; i < cols.size(); ++i) {
            cols[i].push_front(cols[i].back());
            cols[i].pop_back();
        }
    }
}


void rotate(int k) {
    int total = 2 * M + 2 * N - 4;
    k = k % total;
    if (k == 0) return;

    for (int T = 0; T < k; ++T) {
        int tl = cols[0].front();
        cols[0].pop_front();
        rows.front()->push_front(tl);

        int tr = rows.front()->back();
        rows.front()->pop_back();
        cols[1].push_front(tr);

        int br = cols[1].back();
        cols[1].pop_back();
        rows.back()->push_back(br);

        int bl = rows.back()->front();
        rows.back()->pop_front();
        cols[0].push_back(bl);
    }
}


void convert(vvi board) {
    N = board.size();
    M = board[0].size();

    cols.resize(2);

    for (int i = 0; i < N; ++i) {
        list<int> *t = new list<int>();
        for (int j = 0; j < M; ++j) {
            if (j == 0 || j == M - 1) {
                int id = j != 0;
                cols[id].push_back(board[i][j]);
                continue;
            }
            t->push_back(board[i][j]);
        }
        rows.push_back(t);
    }
}


void apply(vvi& board) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (j == 0 || j == M - 1) {
                int id = j != 0;
                board[i][j] = cols[id].front();
                cols[id].pop_front();
                continue;
            }
            board[i][j] = rows.front()->front();
            rows.front()->pop_front();
        }
        delete rows.front();
        rows.pop_front();
    }
}


vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
    int Rn = 0, Sn = 0;
    convert(rc);
    for (auto s : operations) {
        if (s[0] == 'R') {
            ++Rn;
            shift(Sn);
            Sn = 0;
        }
        else {
            ++Sn;
            rotate(Rn);
            Rn = 0;
        }
    }
    
    shift(Sn);
    rotate(Rn);

    apply(rc);
    return rc;
}

 

효율성 실패

#include <string>
#include <vector>

using namespace std;
using vvi = vector<vector<int>>;

void shift(vvi &rc, int k) {
    if (k == 0) return;
    int n = rc.size();
    vvi board = rc;
    for (int i = 0; i < rc.size(); ++i) rc[(i + k) % n] = board[i];
}


void rotate(vvi &rc, int k) {
    if (k == 0) return;
    int n = rc.size(), m = rc[0].size();
    int len = 2 * n + 2 * m - 4;

    vector<pair<int, int>> pos(len);
    for (int i = 0; i < pos.size(); ++i) {
        if (i < m) pos[i] = { 0, i };
        else if (i < m + n - 1) pos[i] = { i - m + 1, m - 1 };
        else if (i < m + n - 1 + m - 1) pos[i] = { n - 1, m - 1 + n - 1 + m - 1 - i };
        else pos[i] = { m - 1 + n - 1 + m - 1 + n - 1 - i, 0 };
    }

    k = k % len;

    auto Y = [&](int i) {
        return pos[(i + len - k) % len].first;
    };
    auto X = [&](int i) {
        return pos[(i + len - k) % len].second;
    };

    vvi board = rc;

    for (int i = 0; i < pos.size(); ++i) {
        if (i < m) rc[0][i] = board[Y(i)][X(i)];
        else if (i < m + n - 1) rc[i - m + 1][m - 1] = board[Y(i)][X(i)];
        else if (i < m + n - 1 + m - 1) rc[n - 1][m - 1 + n - 1 + m - 1 - i] = board[Y(i)][X(i)];
        else rc[len - i][0] = board[Y(i)][X(i)];
    }
    return;
}

vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
    int countR = 0, countS = 0;
    for (auto s : operations) {
        if (s[0] == 'R') {
            ++countR;
            shift(rc, countS);
            countS = 0;
        }
        else {
            ++countS;
            rotate(rc, countR);
            countR = 0;
        }
    }

    if (countR) rotate(rc, countR);
    if (countS) shift(rc, countS);

    return rc;
}


int main() {
    solution({{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} , {"Rotate"});
    return 0;
}