[백준/JAVA] 1406_에디터

백준🔗

1406번: 에디터

 

 

문제

 

 

간단 풀이

어제 들은 특강에서 연결리스트를 배워가지고 연습을 위해 연결 리스트 풀어보는 중~!

 

문제를 보면 커서 이동을 따라가면서 지정된 자리에서 삽입/삭제가 이루어지기 때문에 random access를 할 일이 없다. 따라서 배열보다는 연결리스트가 유리하다고 판단했고, 왼쪽/오른쪽 이동이 있기 때문에 Doubly LinkedList로 구현해서 풀었다.

 

nodePool은 메모리 풀을 활용한 정적 할당을 위해 만들었다. 사용할 노드들을 처음에 한꺼번에 할당한 뒤, 필요할 때 꺼내 쓰는 방식이다. 실제 프로그램을 개발할 때는 동적 할당을 해야겠지만, 알고리즘을 풀 때는 정적 할당을 활용하는 것이 수행 시간 측면에서 유리하다고 한다!

 

<메모리 풀의 장점>

1. 동적 할당을 하는 오버헤드가 없어진다.
2. 사용이 끝날 때마다(특히 여러 개의 테스트 케이스가 있는 경우) 메모리를 해제할 필요가 없다.
3. 모든 노드가 메모리 상에서 뭉쳐 있기 때문에 캐시 효율이 높아진다.

 

노드를 기준으로 커서가 오른쪽에 위치해있다고 생각을 하고 코드를 구현했는데, 커서가 맨 앞에 있는 경우를 위해 head에 더미 노드를 만들어 두었다. 

 

+ 그동안 계속 Scanner를 써왔지만, 이제는 BufferedReader, Writer도 연습을 해봐야겠다는 생각이 들어서 당분간은 버퍼드를 사용할 예정이다!

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static class Node {
		char data;
		Node prev, next;

		public Node() {

		}

		public Node(char data) {
			this.data = data;
		}
	}

	static class DoublyLinkedList {
		Node head;
		Node tail;
		Node cur;
		Node[] nodePool;
		int nodeCnt;

		public DoublyLinkedList() {
			nodePool = new Node[600000];
			head = new Node(); // 더미 노드
			tail = head;
			cur = tail;
		}

		Node getNewNode(char data) {
			nodePool[nodeCnt] = new Node(data);
			return nodePool[nodeCnt++];
		}

		// 왼쪽으로 한 칸 이동 (맨 앞이면 무시)
		void moveLeft() {
			if (cur == head) {
				return;
			}
			cur = cur.prev;
		}

		// 오른쪽으로 한 칸 이동 (맨 뒤면 무시)
		void moveRight() {
			if (cur == tail) {
				return;
			}
			cur = cur.next;
		}

		// 왼쪽 문자 삭제 (맨 앞이면 무시)
		void delete() {
			if (cur == head) {
				return;
			}
			if (cur == tail) {
				cur.prev.next = null;
				cur = cur.prev;
				tail = cur;
				return;
			}
			cur.prev.next = cur.next;
			cur.next.prev = cur.prev;
			cur = cur.prev;
		}

		// 왼쪽에 문자 추가
		void insert(char c) {
			Node newNode = getNewNode(c);
			if (cur == tail) {
				cur.next = newNode;
				newNode.prev = cur;
				cur = cur.next;
				tail = cur;
				return;
			}

			// 추가한 노드 이어주기
			newNode.next = cur.next;
			newNode.prev = cur;
			cur.next.prev = newNode;
			cur.next = newNode;
			// 커서를 추가된 노드 뒤로 이동
			cur = cur.next;
		}

		void print() throws IOException {
			cur = head.next;
			while (cur != null) {
				bw.write(cur.data);
				cur = cur.next;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		DoublyLinkedList list = new DoublyLinkedList();
		char[] init = br.readLine().toCharArray();
		for (char c : init) {
			list.insert(c);
		}

		int M = Integer.parseInt(br.readLine()); // 명령어 개수
		StringTokenizer st;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			char cmd = st.nextToken().charAt(0);
			switch (cmd) {
			case 'L':
				list.moveLeft();
				break;
			case 'D':
				list.moveRight();
				break;
			case 'B':
				list.delete();
				break;
			default:
				char c = st.nextToken().charAt(0);
				list.insert(c);
				break;
			}
		}
		list.print();
		bw.flush();
	}
}

 

 

참고 자료