백준 1406 - 에디터 [자바] [파이썬]

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

1406번: 에디터

---

풀이 과정

문자열이 주어지고, 문자열 안에서 커서를 왼쪽, 오른쪽으로 이동시키며 커서 왼쪽의 문자를 추가하거나 삭제시키는 연산을 구현하는 문제이다.

 

문자열을 배열로 생각한다면 문자열에서 문자를 추가하거나 삭제하는 연산은 O(N)의 시간복잡도를 가진다. 추가된 문자 뒤쪽에 있는 문자를 한 칸씩 밀거나, 삭제된 문자 뒤쪽에 있는 문자들을 한 칸씩 당겨야 하기 때문이다. 따라서 문자의 추가와 삭제가 O(1)에 이루어질 수 있는 링크드 리스트를 사용해 문제를 해결해야 한다.

 

이 문제는 추가, 삭제 연산이 입력으로 들어오는 index에서 이루어 지는 것이 아닌, 커서 왼쪽에서 이루어진다는 것이 고정되어 있으므로 2개의 스택을 활용하여, 왼쪽 스택에는 커서 왼쪽에 있는 문자들을 저장, 오른쪽 스택에는 커서 오른쪽에 있는 문자들을 저장하는 방법으로 문제를 해결할 수도 있다.

---

소스 코드

2개의 스택 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main { // 메모리 : 142208KB / 시간 608ms
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ArrayDeque<Character> lStack = new ArrayDeque<>(); // 커서 왼쪽에 있는 문자들을 lStack에 저장한다
		ArrayDeque<Character> rStack = new ArrayDeque<>(); // 커서 오른쪽에 있는 문자들을 rStack에 저장한다
		char[] str = br.readLine().toCharArray();
		
		for (int i = 0; i < str.length; i++) {
			lStack.addLast(str[i]); // 초기에는 커서가 문자열의 가장 오른쪽에 있으므로 모든 문자를 lStack에 넣는다
		}
		
		int N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			char temp = st.nextToken().charAt(0);
			
			switch (temp) {
			case 'L': // L이 들어오면 커서를 왼쪽으로 한 칸 옮긴다
//				커서 왼쪽에 있는 문자 개수가 줄고, 커서 오른쪽에 있는 문자 개수가 하나 느는것과 같다
//				lStack의 원소를 rStack으로 하나 옮겨준다
				if (!lStack.isEmpty()) rStack.addLast(lStack.pollLast());
				break;
			case 'D': // D가 들어오면 커서를 오른쪽으로 한 칸 옮긴다
//				커서 오른쪽에 있는 문자 개수가 줄고, 커서 왼쪽에 있는 문자 개수가 하나 느는것과 같다
//				rStack의 원소를 lStack으로 하나 옮겨준다
				if (!rStack.isEmpty()) lStack.addLast(rStack.pollLast());
				break;
			case 'B': // B가 들어오면 커서 왼쪽에 있는 문자가 하나 없어진다
				if (!lStack.isEmpty()) lStack.pollLast(); // lStack에서 원소를 하나 제거해준다
				break;
			case 'P': // P가 들어오면 다음 오는 문자를 커서 왼쪽에 붙인다
				char temp2 = st.nextToken().charAt(0);
				lStack.addLast(temp2); // 다음 오는 문자를 lStack에 하나 넣어준다
				break;
			}
		}
		
		
//		lStack의 모든 문자를 rStack으로 옮긴 후, rStack의 모든 문자를 pop() 하면서 출력해주면 문자열을 출력할 수 있다
		while (!lStack.isEmpty()) {
			rStack.addLast(lStack.pollLast());
		}
		
		while (!rStack.isEmpty()) {
			sb.append(rStack.pollLast());
		}
		
		System.out.print(sb.toString());
	} // end of main
} // end of class

 

2개의 스택 - 파이썬

import sys
input = sys.stdin.readline

# 메모리 38664KB / 시간 620ms

l_stack = list(map(str, input().rstrip()))
r_stack = []
N = int(input())

for i in range(N):
    command = input().split()
    if command[0] == "L":
        if len(l_stack) != 0:
            r_stack.append(l_stack.pop())
    elif command[0] == "D":
        if len(r_stack) != 0:
            l_stack.append(r_stack.pop())
    elif command[0] == "B":
        if len(l_stack) != 0:
            l_stack.pop()
    elif command[0] == "P":
        l_stack.append(command[1])

while len(l_stack) > 0:
    r_stack.append(l_stack.pop())

while len(r_stack) > 0:
    print(r_stack.pop(), end="")

 

링크드 리스트 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

public class Main { // 메모리 118980KB / 시간 624ms
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] str = br.readLine().toCharArray();
		int N = str.length;
		LinkedList<Character> ll = new LinkedList<>();
		
		for (int i = 0 ; i < N; i++) {
			ll.add(str[i]);
		}
		
		ListIterator<Character> iter = ll.listIterator(); // 리스트에서 커서 위치를 저장할 ListIterator을 만든다
		
		while (iter.hasNext()) { // 
			iter.next(); // iter에 대입해줄 필요 없이 알아서 iter를 다음으로 넘겨줌
		}
		
		int M = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			char temp = st.nextToken().charAt(0);
			switch (temp) {
			case 'L':
				if (iter.hasPrevious()) iter.previous(); // 링크드리스트에 이전 노드가 있으면 그 노드를 가리키도록 함
				break;
			case 'D':
				if (iter.hasNext()) iter.next(); // 링크드리스트에 다음 노드가 있으면 그 노드를 가리키도록 함
				break;
			case 'B':
				if (iter.hasPrevious()) { // 링크드 리스트에 이전 노드가 있으면 그 노드를 가리킨 뒤 지움
					iter.previous();
					iter.remove();
				}
				break;
			case 'P':
				char temp2 = st.nextToken().charAt(0);
				iter.add(temp2); // 링크드의 현재 가리키고 있는 노드의 index에 temp2가 오도록 추가함
				break;
			}
		}
		
		for (char c : ll) {
			sb.append(c);
		}
		
		System.out.print(sb.toString());
		
	} // end of main
} // end of class