백준 1406번: 에디터 [자료구조][리스트] -Java

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

1406번: 에디터

자료구조의 특성에 대해서 잘 알아야 풀 수 있는 문제..

LinkendList는 삽입,삭제는 이터레이터를 이용하면 빠르고, idx를 통한 검색은 너무나 느리다! 이터레이터를 적극활용.

 

시간초과를 해결하기 위한 늪에 빠졌다가 겨우나왔다.

ListIterator의 메소드에 대해 다시 익혀볼 것..!

- iterator의 remove() 메소드는 마지막으로 반환했던 요소를 삭제하는 것. 

- 처음 이터레이터 객체를 받은 후 next() , previous()를 해야 그때부터 본격적으로 요소를 가리키게 되는 것.

 

 

<Java 코드>

import java.io.*;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		String str = st.nextToken();
		
//		ArrayList<Character> list = new ArrayList<Character>();
		LinkedList<Character> list = new LinkedList<Character>();
		
		for (int i = 0; i < str.length(); i++) {
			list.add(str.charAt(i));
		}
		
		
		st= new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		
		ListIterator<Character> it = list.listIterator(list.size());
		
		
		for (int tc = 0; tc < M; tc++) {
			
			//명령어 받기
			st = new StringTokenizer(br.readLine());
			char cmd = st.nextToken().charAt(0);
			
			if(cmd == 'P') {
				char ch = st.nextToken().charAt(0);
				it.add(ch);
				
			} else if (cmd == 'L') {
				if(it.hasPrevious()) it.previous();
			} else if (cmd == 'D') {
				if(it.hasNext()) it.next();
			} else if (cmd == 'B'){
				//remove()메소드는 가장 마지막으로 반환한 요소를 삭제하는 것이다.
				if(it.hasPrevious()) {
					it.previous();
					it.remove();
				}
			}
//			System.out.println(list.toString() + " "+ cmd);
			
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (Character ch : list) {
//			System.out.print(list.get(i));
			bw.write(ch);
		}
		bw.flush();
		
		
	}

}

System.out.println에서 BufferedWriter로도 바꿨지요..

 

728x90

 

idx를 통한 for문 for (int i = 0; i< N ; i++) 을 사용하면, idx기반으로 요소를 찾는 것이기에

ArrayList에서는 효율적이지만 LinkedList에서는 쥐약이다.

(링크드리스트는 항상 head부터 탐색해야함.. 왜? 다음 노드정보를 그 앞전 노드만 갖고있거던..)

 

그래서 향상된 for문을 사용해서 이터레이터를 써야한다. for-each.

 

LinkedList기준으로 시간복잡도를 생각해보면

idx를 통한 for문은 O(N^2) --- idx를 통한 요소 검색 O(N)

향상된 foreach문은 O(N)  --- iterator를 통한 요소 검색 O(1)