백준 1406 c++ "에디터" -PlusUltraCode-

https://www.acmicpc.net/problem/1406

 

[필자 사고]

자료구조인 연결리스트를 이용하면 시간 복잡도 O(1)만에 풀 수 있어서

N이 100000이라 시간초과가 안나고 해결할 수 있따.

필자는 c++ 에 내장 된 라이브러리인 연결리스트를 이용하여 해당 문제를 타파했따.

 

아래는 자세한 코드해설이다.

[코드 해설]

• 1. Input() 함수
  • 역할: 초기 문자열을 받아 myList라는 list<char> 컨테이너에 한 글자씩 저장하고, 명령어 개수 N을 입력받는다.
  • 세부 동작:
    • 문자열을 순회하면서 각 문자들을 리스트에 push_back()으로 삽입.
    • 이후 명령의 수 N을 입력받음.

  ---

  2. Game_Start() 함수
  • 역할: 커서의 위치를 추적하면서 N개의 명령을 처리.
  • 커서 초기화: auto it = myList.end();로 커서를 문자열 맨 끝에 둔다.
  • 명령 처리: for 루프를 통해 N개의 명령을 반복 처리한다.
  명령어 종류
  1. L (왼쪽 이동)
     • 커서를 왼쪽으로 이동 (it = prev(it))
     • 단, 이미 맨 앞이면 무시.
  2. D (오른쪽 이동)
     • 커서를 오른쪽으로 이동 (it = next(it))
     • 단, 이미 맨 끝이면 무시.
  3. B (삭제)
     • 커서 왼쪽 문자를 삭제.
     • prev(it)를 구해 erase()로 제거.
     • 맨 앞에서는 아무 동작도 하지 않음.
  4. P x (삽입)
     • 현재 커서 위치 앞에 문자 x 삽입 (insert(it, x))

  ---

  3. 출력 부분
  • 모든 명령 처리 후, myList를 순회하며 모든 문자를 출력.

  ---

  4. main() 함수
  • Input()으로 초기화
  • Game_Start()로 로직 실행

  ---

  💡 전반적 설명
  • std::list<char>를 사용해 중간 삽입/삭제가 **O(1)**로 빠르게 동작하도록 함.
  • iterator를 커서처럼 사용하여, 문자열 편집기 동작을 시뮬레이션 함.
  • C++ STL의 prev(), next() 등의 함수 활용이 포인트.

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <list>
using namespace std;

string str;
int N;
list<char> myList;
void Input() {
	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		myList.push_back(str[i]);
	}
	cin >> N;
	
}

void Game_Start() {
	auto it = myList.end();
	for (int i = 0; i < N; i++) {
		char ch;
		cin >> ch;

		if (ch == 'L') {
			if (it==myList.begin())continue;
			it = prev(it);
		}
		else if (ch == 'D') {
			if (it == myList.end())continue;
			it = next(it);
		}

		else if (ch == 'B') {
			if (it == myList.begin())continue;
			auto removeIt = prev(it);
			myList.erase(removeIt);
		}
		else if(ch=='P'){
			char inputData;
			cin >> inputData;

			myList.insert(it,inputData);
		}
	}

	for (auto it = myList.begin(); it != myList.end(); it++) {
		cout << *it;
	}
}

int main(void) {
	Input();
	Game_Start();
}