백준 온라인 저지 | 1406번 에디터 | C++

백준 온라인 저지 | 1046번 에디터 | C++

1406번: 에디터

 

1. 문제 정의

■ 1.1 리스트 반복자

 편집기에는 커서(cursor)라는 것이 있는데 커서는 첫 번째 문자의 왼쪽, 마지막 문자의 오른쪽, 혹은 모든 연속된 두 문자 사이에 위치할 수 있다. 그리고 편집기가 지원하는 4가지 명령어로 커서의 위치를 좌우로 옮기거나 문자를 삽입 혹은 제거할 수 있다. 이러한 특성을 고려해보았을 때, 문장은 리스트(list), 커서는 반복자(iterator)로 적절하게 구현하면 위의 조건을 만족시킬 수 있다.

 

■ 1.2 리스트 메서드

 리스트와 그 반복자를 통해 에디터를 구현할 것이기 때문에 각 명령어를 구현하는 데 사용할 메서드를 알고 있어야 한다. 우선, 커서를 왼쪽으로 옮기는 L 명령어는 반복자(이하 iterator)에 operator--를 적용하고, 커서를 오른쪽으로 옮기는 D 명령어는 반복자에 operator++를 적용한다. 이때, 리스트 반복자는 랜덤 액세스를 지원하지 않으므로 덧셈 연산과 뺄셈 연산을 할 수 없다는 것을 꼭 기억한다. 가령, 커서를 왼쪽으로 세 번 옮기고 싶어서 iterator - 3와 같은 연산을 할 수 없다. 다음으로 커서 왼쪽에 있는 문자를 삭제하는 B 명령어는 erase 메서드를 사용한다. erase 메서드는 반복자가 가리키는 원소를 리스트에서 없애고 다음 원소를 가리키는 반복자를 반환한다. 마지막으로 커서 왼쪽에 문자를 추가하는 P 명령어는 insert 메서드를 사용한다. insert 메서드는 반복자가 가리키는 위치에 원소를 추가한다.

 

2. 문제 풀이

■ 2.1 풀이 가이드

1. 문자열 N과 명령어 개수 M을 입력받고 문자열 N으로 문장을 나타낼 리스트 l을 초기화한다.
2. 커서를 나타낼 반복자 cursor를 end 메서드로 리스트의 마지막 원소 다음을 가리키도록 한다.
3. 명령어를 입력받고 switch문으로 명령어를 각각 구분한다. 명령어의 개수만큼 다음 과정을 반복한다.
   • L 명령어는 operator--로 반복자를 왼쪽으로 이동시킨다.
   • D 명령어는 operator++로 반복자를 오른쪽으로 이동시킨다.
   • B 명령어는 operator--로 반복자를 왼쪽으로 이동시키고 erase 메서드로 문자를 삭제한다. erase 메서드에서 반환된 값을 반복자에 대입하여 반복자가 다음 원소를 가리키게 한다.
   • P 명령어는 문자 word를 입력받아 반복자가 가리키는 위치에 insert 메서드로 문자를 삽입한다.
4. 리스트 l을 순서대로 출력한다.

 

■ 2.2 시간 복잡도와 공간 복잡도

 리스트를 통해 구현한 에디터는 문자를 삽입하거나 삭제하는 데 O(1)의 시간 복잡도를 가진다.

 

3. 문제 해결

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// 문자열 N과 명령어 개수 M을 입력받습니다.
	string N;
	int M;
	cin >> N >> M;

	// 입력받은 문자열 N을 리스트에 한 글자씩 저장합니다.
	list<char> l;
	for (int i = 0; i < N.size(); ++i) {
		l.push_back(N[i]);
	}
	// 커서(반복자)의 위치를 리스트 end로 설정합니다.
	auto cursor = l.end();
	
	// 명령어를 입력받습니다.
	for (int i = 0; i < M; ++i) {
		char cmd;
		cin >> cmd;
		
		switch (cmd) {
		//  커서를 왼쪽으로 한 칸 옮깁니다.
		case 'L':
			if (cursor != l.begin()) { cursor--; }
			break;
		// 커서를 오른쪽으로 한 칸 옮깁니다.
		case 'D':
			if (cursor != l.end()) { cursor++; }
			break;
		// 커서 왼쪽의 문자를 삭제합니다.
		case 'B':
			if (cursor != l.begin()) { cursor = l.erase(--cursor); }
			break;
		// 커서 왼쪽에 문자를 삽입합니다.
		case 'P':
			char word;
			cin >> word;
			l.insert(cursor, word);
			break;
		}
	}
	
	// 리스트에 저장된 문자를 순서대로 출력합니다.
	for (auto iter = l.begin(); iter != l.end(); ++iter) {
		cout << *iter;
	}
	return 0;
}

 

그림 1406번 에디터 성공

 

4. 문제 고찰

■ 4.1 리스트 생성자

 이 문제에서 입력받은 문자열 N으로 리스트 l를 초기화할 때 for문을 사용하여 글자마다 push_back 메서드를 호출하였다. 하지만 string 반복자를 리스트 생성자에 전달하여 호출하면 더 손쉽게 초기화할 수 있다.

// 리스트 l의 생성자에 문자열 N의 반복자를 전달하여 초기화합니다.
list<char> l(N.begin(), N.end());

 

■ 4.2 erase 메서드

 커서 왼쪽의 문자를 삭제하는 B 명령어를 수행할 때 erase 메서드를 사용하였다. erase 메서드는 다음과 같이 특정한 위치의 원소 또는 특정한 범위의 원소를 제거한다. 여기서 Where는 리스트에서 없앨 원소의 위치를 나타내고 first와 last는 각각 리스트에서 없앨 첫 번째 원소의 위치와 마지막 원소의 다음 위치를 나타낸다.

iterator erase(iterator Where);
iterator erase(iterator first, iterator last);

 또한, erase 메서드는 삭제될 원소 다음 원소를 가리키는 반복자나, 남아있는 원소가 없는 경우 리스트 end를 가리키는 포인터를 반환한다. 처음 코드를 작성했을 때, erase 메서드에서 반환된 값을 반복자에 대입하지 않는 바람에 반복자가 다음 원소를 가리키지 못해 런타임 에러가 발생했다. erase 메서드를 사용할 때는 포인터가 반환된다는 사실을 꼭 기억하길 바란다.