[프로그래머스] 표 편집 C++

 

코딩테스트 연습 - 표 편집

 

 

문제풀이

 

2021 카카오 채용연계형 인턴십 코딩테스트 문제로 나왔다.

코테 때도 시간초과가 나서 해결을 하지 못했는데 다시 풀어도 그렇다,,

 

 

2021 카카오 인턴십 for Tech developers 코딩 테스트 해설

 

처음에는 벡터로 풀었는데 정확성 테스트는 다 통과했지만 효율성 테스트는 빵점,,,

카카오 기술블로그의 코딩 테스트 해설을 참고해서 풀어보았다.

아래 코드는 정확성은 모두 통과하고 효율성 테스트는 9, 10번만 통과한 코드다.

내일 다시 도전!!

 

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

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    vector<bool> deleted(n); // true : 삭제된 행
    vector<int> st;
    list<int> table;

    for (int i = 0; i < n; i++) table.push_back(i);

    auto cur = table.begin();
    for (int i = 0; i < k; i++) cur++;

    for (int i = 0; i < cmd.size(); i++) {
        if (cmd[i][0] == 'U') {
            for (int j = 0; j < stoi(cmd[i].substr(2)); j++) {
                cur--;
            }
        }
        else if (cmd[i][0] == 'D') {
            for (int j = 0; j < stoi(cmd[i].substr(2)); j++) {
                cur++;
            }
        }
        else if (cmd[i][0] == 'C') {
            deleted[*cur] = true;
            st.push_back(*cur);

            auto now = cur;

            if (*cur == table.back()) cur--;
            else cur++;
            table.erase(now);
        }
        else if (cmd[i][0] == 'Z') {
            deleted[st.back()] = false;
            table.push_back(st.back());
            table.sort();
            st.pop_back();
        }
    }

    string answer = "";
    for (int i = 0; i < deleted.size(); i++) {
        if (deleted[i]) answer += 'X';
        else answer += 'O';
    }
    return answer;
}

 

 

Z 명령어를 수행할 때 들어갈 자리를 찾는 것에 시간이 많이 걸리는 것 같다.

코드를 고쳤는데도 계속 시간초과 떠서 아래 블로그를 참고해서 풀어봤다.

 

[프로그래머스 Lv3] 표 편집(with Swift)

 

prev, next 배열을 만들어서 링크드 리스트처럼 이전 행과 다음 행 정보를 관리해주었다.

행을 삭제하면 이전 행과 다음 행을 연결해주면 되고 행을 복구하면 해당 행을 다시 연결해주면 된다.

모든 명령어를 수행한 뒤에 스택에 남아있는 행들은 X 처리해주면 끝!

 

 

C++ 코드

 

	#include <string>
	#include <vector>
	#include <stack>
	using namespace std;
	string solution(int n, int k, vector<string> cmd) {
	stack<int> st; // 삭제된 행
	vector<int> prev;
	vector<int> next;
	for (int i = 0; i < n + 2; i++) {
	prev.push_back(i - 1);
	next.push_back(i + 1);
	}
	k++;
	for (int i = 0; i < cmd.size(); i++) {
	if (cmd[i][0] == 'U') {
	for (int j = 0; j < stoi(cmd[i].substr(2)); j++) {
	k = prev[k];
	}
	}
	else if (cmd[i][0] == 'D') {
	for (int j = 0; j < stoi(cmd[i].substr(2)); j++) {
	k = next[k];
	}
	}
	else if (cmd[i][0] == 'C') {
	st.push(k);
	next[prev[k]] = next[k];
	prev[next[k]] = prev[k];
	if (next[k] == n + 1) k = prev[k];
	else k = next[k];
	}
	else if (cmd[i][0] == 'Z') {
	int r = st.top();
	next[prev[r]] = r;
	prev[next[r]] = r;
	st.pop();
	}
	}
	string answer;
	answer.append(n, 'O');
	while (!st.empty()) {
	answer[st.top() - 1] = 'X';
	st.pop();
	}
	return answer;
	}

view raw [프로그래머스] 표 편집.cpp hosted with ❤ by GitHub