어제 밤에 조금 난이도 있는 문제를 풀어보고자 도전한 문제는 프로그래머스 표 편집 이다. 카카오 인턴십 기출 문제인데 level3 이고 카카오 답게 설명이 매우 길고 문제 조건을 파악하는 데에 시간이 조금 걸렸다.
프로그래머스 표 편집
처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
제한사항
- 5 ≤ n ≤ 1,000,000
- 0 ≤ k < n
- 1 ≤ cmd의 원소 개수 ≤ 200,000
- cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
- X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
- X가 나타내는 자연수에 ',' 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
- cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
- 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
- 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하였으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
- 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
- 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.
- 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.
정확성 테스트 케이스 제한 사항
- 5 ≤ n ≤ 1,000
- 1 ≤ cmd의 원소 개수 ≤ 1,000
효율성 테스트 케이스 제한 사항
- 주어진 조건 외 추가 제한사항 없습니다.
나의 풀이
효율성 테스트가 있는 문제이고 n 값이나 명령어 D, U 가 주어질 때 이동 값이 크기 때문에 단순한 일차원 배열이나 벡터를 사용해서는 통과할 수 없을 것 같았다.
또 중간에 위치한 데이터를 삭제하고 다시 넣는 과정이 있기 때문에 더더욱 단순 배열이나 벡터는 적합하지 않다.
중간에 데이터를 넣고 빼야하는 것을 생각해 나는 링크드리스트를 떠올렸다. 자바에는 적절한 자료형이 있는 것 같던데 c++ 에도 있나 찾아보니 <list> 자료형이 존재했고 리스트를 사용해서 코드를 작성하였다.
중간에 데이터를 넣고 빼는 코드가 필요한 것은 명령어 C, Z 를 입력했을때를 위함인데 특히나 Z 입력시에는 삭제되었던 데이터들을 역순으로 복원 시키는 작업이 필요했다. 처음엔 Z 명령어가 연속으로 입력될 수 있는지를 몰라서 썼던 코드를 지우고 <stack> 자료구조를 사용해서 작성하였다.
하지만 리스트를 사용해서는 효율성 테스트를 통과하지 못했다. 아무래도 D, U 명령어 수행시 표에서 가리키고 있는 위치를 이동 시키는게 선형적으로 진행될 수 밖에 없기 때문인 것 같았다. 입력되는 이동 값이 n 이라면 무조건 n 칸을 이동해야 하기 때문이다.
이 과정의 시간 복잡도를 줄이는 방법은 보통 log n 의 이동 시간을 보장하는 것이 유력하다. 찾아보니 <set> 을 사용한 경우가 있었다. <set> 자료구조는 균형 이진트리 형태로 구성되어 있기 때문에 데이터를 넣으면 알아서 정렬되고 데이터를 찾아 가는 과정도 log n 의 시간 복잡도를 보장하기 때문에 효율성 테스트를 만족할 수 있었다.
<set> 을 사용해서 다시 코드를 수정했고 참고한 포스팅에서 <set> 의 원소를 가리키는 포인터 <set>::iterator 를 앞뒤로 움직이는 함수 prev 와 next 를 사용하는 방법도 알 수 있었다.
여러모로 배운 내용이 많은 문제였다...!
코드
#include <iostream>
#include <vector>
#include <set>
#include <stack>
// 프로그래머스 표 편집, level 3
using namespace std;
string solution(int n, int k, vector<string> cmd) {
string answer(n, 'X');
set<int> table; // 균형 이진트리 기반
stack<int> deleted;
for (int i = 0; i < n; ++i) table.insert(i);
auto iter = table.find(k);
for (int i = 0; i < cmd.size(); ++i) {
char command = cmd[i][0];
if (command=='D'){ // 아래로
int down = stoi(cmd[i].substr(2,cmd[i].size()-2));
while (down>0){
iter = next(iter);
down--;
}
}else if (command=='U'){ // 위로
int up = stoi(cmd[i].substr(2,cmd[i].size()-2));
while (up>0){
iter = prev(iter);
up--;
}
}else if (command=='C'){ // 삭제
//현재 포인터가 가리키는 데이터 삭제, 삭제된 데이터 스택에 push
deleted.push(*iter);
iter = table.erase(iter);
// erase -> 삭제된 데이터 이후의 포인터를 가리킴
// 제일 끝 데이터를 삭제 했다면 마지막 데이터를 가리키도록
if (iter==table.end()) iter = prev(iter);
}else{ // 복구
table.insert(deleted.top());
deleted.pop();
}
}
for(int i : table) answer[i] = 'O'; // 현재 set 에 남아있는 자료만 체크
return answer;
}
Reference
