2021 카카오 채용연계형 인턴십표 편집

1. 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO"

programmers.co.kr

0 ~ n-1까지의 n개의 원소를 가진 표에 대해 편집을 하는 문제이다.

편집 명령어는 아래와 같다.

"U X" : 위로 X만큼 이동
"D X" : 아래로 X만큼 이동
"C" : 지금 있는 위치의 원소 삭제
"Z" : 가장 최근에 삭제했던 원소 복원

처음 접근했던 방식은, 아래와 같았다.

길이 n의 배열을 선언 후 모두 "O"로 초기화한다.

위치 이동은 인덱스 기반으로 수행한다.

삭제는 지금 위치의 값을 "X"로 초기화 하고 지금 위치를 스택에 push 한다.

복원은 스택의 원소를 하나 가져와 그 위치의 값을 "O"로 만든다.

위 방식대로 할 경우 처음에 생각한 시간 복잡도는 아래와 같았다.

"U X" : 위로 X만큼 이동 => [지금 위치 - X)] 통해 O(1) 만에 수행
"D X" : 아래로 X만큼 이동 => [지금 위치 + X]를 통해 O(1)만에 수행
"C" : 지금 있는 위치의 원소 삭제 => 지금 위치의 값을 "X"로 갱신하면 O(1)만에 수행
"Z" : 가장 최근에 삭제했던 원소 복원 => 스택에 원소 하나 가져와서 값을 "O"로 갱신하면 O(1)만에 수행

그런데 이동의 경우 다시 생각해보니 "X"로 표시된 개수를 제외해야 하는 문제가 있었다!

따라서 어쩔 수 없이 인덱스 기반으로 한 번에 이동하지 못하고 하나하나 "X"를 확인하며 이동해야 했다.

이는 최악의 경우 매 이동마다 O(n)의 시간이 소요될 수 있음을 의미한다.

정리하면 최악의 경우 시간 복잡도는 아래와 같다.

"U X" : 위로 X만큼 이동 => O(n)
"D X" : 아래로 X만큼 이동 => O(n)
"C" : 지금 있는 위치의 원소 삭제 => O(1)
"Z" : 가장 최근에 삭제했던 원소 복원 => O(1)

하지만 다른 방법이 생각나지 않아서 위 생각대로 풀었다...

2. 풀이

1. 처음 효율성 통과 못한 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

void init(string& answer, stack<int>& posStack, const int& n) {

	for (int i = 0; i < n; i++)
		answer.push_back('O');
}

void moveUp(int& currentPos, int diff, const string& answer) {
	//currentPos에서 diff만큼 위로 이동
	while (diff > 0) {
		currentPos--;
		if (answer[currentPos] == 'O')
			diff--;
	}
}

void moveDown(int& currentPos, int diff, const string& answer) {
	//currentPos에서 diff만큼 아래로 이동
	while (diff > 0) {
		currentPos++;
		if (answer[currentPos] == 'O')
			diff--;
	}
}

string solution(int n, int k, vector<string> cmd) {
	string answer = "";
	stack<int> posStack;
	init(answer, posStack, n);
	int currentPos = k;
	for (int i = 0; i < cmd.size(); i++) {

		if (cmd[i] == "C") {          //삭제
			answer[currentPos] = 'X';
			posStack.push(currentPos);
			int nextPos = currentPos;
			bool flag = false;
			while (nextPos < n) {
				nextPos++;
				if (answer[nextPos] == 'O') {
					currentPos = nextPos;
					flag = true;
					break;
				}
			}
			if (flag)
				continue;

			nextPos = currentPos;
			while (nextPos >= 0) {
				nextPos--;
				if (answer[nextPos] == 'O') {
					currentPos = nextPos;
					break;
				}
			}
		}
		else if (cmd[i] == "Z") {     //복구
			answer[posStack.top()] = 'O';
			posStack.pop();
		}
		else {
			char operation = cmd[i][0];
			int diff = stoi(cmd[i].substr(2));
			if (operation == 'U')                //위로 이동
				moveUp(currentPos, diff, answer);
			else {                               //아래로 이동
				moveDown(currentPos, diff, answer);
			}
		}
	}
	return answer;
}

역시나 정확성은 통과하지만 효율성은 통과하지 못하였다.

어떻게 이동시 발생하는 O(n)의 시간을 줄일 수 있을지 더 고민해 보던 중 링크드 리스트 방식이 떠올랐다.

일반적으로 링크드 리스트는 원소를 추가할 때 특정 위치를 찾아가야 하기 때문에 O(n)의 시간이 걸릴 수 있다.

그런데, 이 문제의 경우 일반적인 원소 추가가 아니라 과거에 삭제된 원소를 복원하는 것이다.

이중 연결 리스트로 구현된 링크드 리스트에서 특정 원소를 삭제한다는 것은, 그 원소를 완전히 지우는 것이 아니라 해당 원소의 양쪽 원소의 포인터만 조정하는 개념이다.

즉, 삭제된 원소는 여전히 양쪽 원소를 가리킨 체 메모리에 존재하고 있다.

이 점에 착안하여, 삭제된 원소의 포인터를 스택에 push 해두고 복원 시 해당 스택을 조회하여 원소를 얻고 양쪽 노드를 찾아 다시 연결하도록 하면 삭제와 복원 모두 O(1) 시간에 가능하다!

정리하면 링크드 리스트의 경우 각 명령에 대한 시간 복잡도는 아래와 같다.

"U X" : 위로 X만큼 이동 => 최악의 경우 O(n) / 삭제된 원소가 많을수록 줄어든다.
"D X" : 아래로 X만큼 이동 => 최악의 경우 O(n) / 삭제된 원소가 많을 수록 줄어든다.
"C" : 지금 있는 위치의 원소 삭제 => O(1)
"Z" : 가장 최근에 삭제했던 원소 복원 => O(1)

주목할 점은, 링크드 리스트 방식을 써도 이동 시 발생하는 최악의 비용은 O(n)이라는 점이다.

다만 삭제된 원소의 경우 자연스럽게 탐색에서 제외시킬 수 있기 때문에 일반적인 경우에서 처음 생각했던 방식보다 좋을 수 있다.

2. 효율성 통과한 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

class Node {
public:
	int val;
	Node* left, *right;

	Node() {};
	Node(int val, Node* left, Node* right) {
		this->val = val;
		this->left = left;
		this->right = right;
	};
};

class List {
private:
	Node* head;
	Node* tail;
	Node* current;

public:
	List(int val) {
		this->head = new Node(val, nullptr, nullptr);
		this->tail = this->head;
		this->current = head;
	};

	void push_back(Node* n) {
		this->tail->right = n;
		n->left = this->tail;
		this->tail = n;
	}

	void moveUp() {
		current = current->left;
	}

	void moveDown() {
		current = current->right;
	}

	Node* getHead() {
		return this->head;
	}

	Node* getCurrent() {
		return this->current;
	}

	Node* deleteCurrent() {
		Node* returnVal;
		Node* leftNode = current->left;
		Node* rightNode = current->right;
		if (rightNode != nullptr && leftNode != nullptr) {
			leftNode->right = rightNode;
			rightNode->left = leftNode;

			returnVal = this->current;
			this->current = rightNode;
		}
		else if (rightNode == nullptr) {
			leftNode->right = nullptr;

			returnVal = this->current;
			this->current = leftNode;
			this->tail = this->current;
		}
		else {
			rightNode->left = nullptr;

			returnVal = this->current;
			this->current = rightNode;
			this->head = this->current;
		}
		return returnVal;
	}


	void Recover(Node* recoverNode) {
		Node* leftNode = recoverNode->left;
		Node* rightNode = recoverNode->right;
		
		if (leftNode == nullptr) {
			rightNode->left = recoverNode;
			this->head = recoverNode;
		}
		else if (rightNode == nullptr) {
			leftNode->right = recoverNode;
			this->tail = recoverNode;
		}
		else {
			leftNode->right = recoverNode;
			rightNode->left = recoverNode;
		}
	}
};

stack<Node*> s;


string solution(int n, int k, vector<string> cmd) {
	string answer = "";
	List* list = new List(0);
	for (int i = 1; i < n ; i++)
		list->push_back(new Node(i, nullptr, nullptr));

	for (int i = 0; i < k; i++)
		list->moveDown();


	for (int i = 0; i < cmd.size(); i++) {

		if (cmd[i] == "C") {			//삭제
			s.push(list->deleteCurrent());
		}
		else if (cmd[i] == "Z") {		//복구
			list->Recover(s.top());
			s.pop();
		}
		else {
			char operation = cmd[i][0];
			int diff = stoi(cmd[i].substr(2));
			if (operation == 'U') {		//위로 이동
				for (int i = 0; i < diff; i++)
					list->moveUp();
			}
			else {                      //아래로 이동
				for (int i = 0; i < diff; i++)
					list->moveDown();
			}
		}
	}

	for (int i = 0; i < n; i++)
		answer.push_back('X');
	
	Node* node = list->getHead();
	while (node != nullptr){
		answer[node->val] = 'O';
		node = node->right;
	}

	return answer;
}

이 문제의 경우 처음 풀었던 방법과 나중에 풀었던 방법 모두 최악의 시간 복잡도는 같다고 생각한다.

하지만 두 번째 풀이가 탐색 시 삭제된 원소를 제거할 수 있기 때문에 일반적인 경우 더 빠를 수 있다.

사실문제를 처음 본 순간 링크드 리스트를 떠올리지 못한 것은 아니다.

그러나 시간 복잡도를 최악의 경우만 생각해서 처음 방법과 두번째 방법이 별 차이 없을 것이라 단정지었던 것이 문제였다.

알고리즘을 풀 때 무조건 최악의 시간복잡도 기준으로만 생각하지 말고, 최악의 시간 복잡도가 같을 때 일반적인 경우의 복잡도도 고려해 비교할 수 있어야겠다.

'algorithm > programmers' 카테고리의 다른 글

프로그래머스 위클리 챌린지10주차 교점에 별 만들기 (0)	2021.10.13
프로그래머스 위클리 챌린지4주차 직업군 추천하기 (0)	2021.10.06
프로그래머스 위클리 챌린지9주차 전력망을 둘로 나누기 (0)	2021.10.06
2021 카카오 채용연계형 인턴십 > 거리두기 확인하기 (0)	2021.09.29
2021 카카오 채용연계형 인턴십 > 숫자 문자열과 영단어 (0)	2021.09.28

성호의 기술블로그

2021 카카오 채용연계형 인턴십표 편집

1. 문제 링크

2. 풀이

'algorithm > programmers' 카테고리의 다른 글

댓글

티스토리툴바

2021 카카오 채용연계형 인턴십표 편집

1. 문제 링크

2. 풀이

'algorithm > programmers' 카테고리의 다른 글

관련글

댓글

티스토리툴바