Baekjoon_1406_에디터

문제주소: https://www.acmicpc.net/problem/1406

1406번: 에디터

에디터 문제는 다음과 같습니다.

보기에는 크게 어려워 보이지 않아서 다음과 같이 풀었는데 실행은 되지만 시간초과가 됩니다.

아마 제가 리스트에서 사용한 insert()에서 O(n)만큼의 시간을 소요하기 때문에 0.3초 제한에 걸리는 것 같습니다.

Python

import sys

def main():
    my_string_list: list = list(sys.stdin.readline().rstrip()) # strip은 공백을 제거해주는 함수이다.
    repeat_num: int = int(sys.stdin.readline())

    # 데이터 전처리
    cur_locate = len(my_string_list) # 현재 커서의 위치

    for i in range(repeat_num):
        order: str = sys.stdin.readline()
        list_order: list = list(order)

        if (list_order[0] == 'L' and cur_locate != 0):
            cur_locate -= 1

        elif (list_order[0] == 'D' and cur_locate != len(my_string_list)):
            cur_locate += 1

        elif (list_order[0] == 'B' and cur_locate != 0):
            my_string_list.pop(cur_locate)
            cur_locate -= 1

        elif (list_order[0] == 'P'):
            my_string_list.insert(cur_locate, list_order[2]) # 시간제한에 걸리는 부분으로 예상
            cur_locate += 1

    print(''.join(my_string_list))

if __name__=="__main__":
    main()

많이 생각을 해봤지만 떠오르지 않아서 다른 사람들의 풀이를 보니 두개의 list를 사용해서 문제를 풀었습니다.

 

import sys

def main():
    my_str_list1: list = list(sys.stdin.readline().rstrip())
    my_str_list2: list = []

    for _ in range(int(sys.stdin.readline())):
        order: str = list(sys.stdin.readline().rstrip().split())

        if order[0] == 'L':
            if my_str_list1:
                my_str_list2.append(my_str_list1.pop())

        elif order[0] == 'D':
            if my_str_list2:
                my_str_list1.append(my_str_list2.pop())

        elif order[0] == 'B':
            if my_str_list1:
                my_str_list1.pop()

        elif order[0] == 'P':
            my_str_list1.append(order[1])

    my_str_list1.extend(reversed(my_str_list2))
    print(''.join(my_str_list1))

if __name__=="__main__":
    main()

다음과 같이 append와 pop만으로도 풀 수 있더군요. 뭔가 파이썬만의 풀이인 것 같습니다.

C++도 풀어봤습니다.

C++

#include <iostream>
#include <list>

using namespace std;

int main()
{
	ios::sync_with_stdio;
	cin.tie(0);

	string input_str = "";
	int num_repeat;
	char cmd, word;

	// 입력 받기
	cin >> input_str;
	list<char> my_list(input_str.begin(), input_str.end()); // 할당

	auto cur_locate = my_list.end(); // 현재 커서의 위치

	cin >> num_repeat;

	for (int i = 0; i < num_repeat; i++)
	{
		cin >> cmd;

		if (cmd == 'L')
		{
			if (cur_locate != my_list.begin())
				cur_locate--;
		}

		else if (cmd == 'D')
		{
			if (cur_locate != my_list.end())
				cur_locate++;
		}

		else if (cmd == 'B')
		{
			if (cur_locate != my_list.begin())
			{
				cur_locate--;
				cur_locate = my_list.erase(cur_locate);
			}
		}

		else if (cmd == 'P')
		{
			cin >> word;
			my_list.insert(cur_locate, word);
		}
	}

	//for (auto ele : my_list)
	//	cout << ele;

	for (cur_locate = my_list.begin(); cur_locate != my_list.end(); cur_locate++)
		cout << *cur_locate;
}