📚 오늘의 문제.

📝 문제 1.

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

1. 문제 설명

   에디터를 구현하는 문제이다. 삽입과 삭제가 빈번하게 일어나는 문제이기 때문에 연결리스트를 활용해서 시간복잡도를 줄이는게 포인트이다.

   L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
   D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
   B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
   삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
   P $	$라는 문자를 커서 왼쪽에 추가함

   연산 후 편집기에 입력되어 있는 문자열을 출력

2. 문제 풀이

   [첫 번째 시도] 시간 초과

   커서를 인덱스로 관리하면서 커서가 제일 왼쪽에 있다면 L과 B 연산 무시를, 커서가 제일 오른쪽에 있다면 D 연산을 무시하는 방식으로 구현을 했다. LinkedList를 이용해서 구현을 해서 시간 초과가 나지 않을 줄 알았지만, 시간 초과가 났다.

   import java.io.*;
   import java.util.*;
   
   public class Main {
   	public static void main(String[] args) throws IOException {
   
   		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
   
   		String input = br.readLine();
   		int n = input.length();
   		LinkedList<Character> list = new LinkedList<>();
   		for (char c : input.toCharArray()) {
   			list.add(c);
   		}
   
   		int m = Integer.parseInt(br.readLine());
   		// cursor의 인덱스
   		int cursorIdx = n;
   
   		for (int i = 0; i < m; i++) {
   			String command = br.readLine();
   
   			if (command.startsWith("P ")) {
   				char ch = command.charAt(2);
   				list.add(cursorIdx, ch);
   				cursorIdx += 1;
   				n += 1;
   			} else if (command.equals("L")) {
   				if (cursorIdx == 0) {
   					continue;
   				}
   				cursorIdx -= 1;
   			} else if (command.equals("D")) {
   				if (cursorIdx == n) {
   					continue;
   				}
   				cursorIdx += 1;
   			} else if (command.equals("B")) {
   				if (cursorIdx == 0) {
   					continue;
   				}
   				list.remove(cursorIdx - 1);
   				cursorIdx -= 1;
   				n -= 1;
   			}
   		}
   
   		StringBuilder result = new StringBuilder();
   		for (char c : list) {
   			result.append(c);
   		}
   		bw.write(result.toString());
   		bw.flush();
   		bw.close();
   		br.close();
   	}
   }

   [두 번째 시도] Passed

   커서 위치를 추적하기 위해 ListIterator를 사용하여 삽입 및 삭제 작업을 보다 효율적으로 처리하도록 코드를 수정했다.

   import java.io.*;
   import java.util.*;
   
   public class Main {
   	public static void main(String[] args) throws IOException {
   
   		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
   
   		String input = br.readLine();
   		int n = input.length();
   		LinkedList<Character> list = new LinkedList<>();
   		for (char c : input.toCharArray()) {
   			list.add(c);
   		}
   
   		ListIterator<Character> iter = list.listIterator(n);
   		int m = Integer.parseInt(br.readLine());
   
   		for (int i = 0; i < m; i++) {
   			String command = br.readLine();
   
   			if (command.startsWith("P ")) {
   				char ch = command.charAt(2);
   				iter.add(ch);
   			} else if (command.equals("L")) {
   				if (iter.hasPrevious()) {
   					iter.previous();
   				}
   			} else if (command.equals("D")) {
   				if (iter.hasNext()) {
   					iter.next();
   				}
   			} else if (command.equals("B")) {
   				if (iter.hasPrevious()) {
   					iter.previous();
   					iter.remove();
   				}
   			}
   		}
   
   		StringBuilder result = new StringBuilder();
   		for (char c : list) {
   			result.append(c);
   		}
   		bw.write(result.toString());
   		bw.flush();
   		bw.close();
   		br.close();
   	}
   }
   

🔑  키워드.

1. Index를 사용한 접근:

   • list.add(cursorIdx, ch) 또는 list.remove(cursorIdx - 1) 같은 작업은 리스트의 특정 위치에 접근하여 삽입/삭제O(1)를 한다.
   • 연결 리스트에서 특정 인덱스에 접근하기 위해서는 리스트의 처음부터 해당 인덱스까지 순회해야 하기 때문에 O(n)의 시간이 걸린다.

2. 시간 복잡도 합산:

   • 각 명령마다 O(n)의 시간이 걸리므로, m개의 명령을 처리할 때 최악의 경우 O(m * n)의 시간이 걸리게 된다.

3. ListIterator 사용:

   • ListIterator는 리스트를 양방향으로 순회할 수 있는 인터페이스를 제공한다.
   • 커서 위치를 추적하기 위해 ListIterator를 사용하면, 현재 위치에서의 삽입과 삭제 작업이 O(1)의 시간 복잡도로 처리한다.

4. 커서 이동:

   • iter.previous() 및 iter.next() 메소드는 각각 커서를 앞뒤로 이동하는 데 사용됩니다. 이 작업은 상수 시간 O(1)에 수행된다.
   • 커서 이동 자체가 상수 시간이기 때문에, 커서의 위치를 변경하는 것이 인덱스로 접근하는 방식에 비해 매우 효율적이다.

5. 삽입과 삭제:

   • iter.add(ch)는 현재 커서 위치에 문자를 삽입하는 데 O(1)의 시간이 걸린다.
   • iter.remove()는 현재 커서 위치에서 문자를 삭제하는 데 O(1)의 시간이 걸린다.

시간 복잡도 요약

• 첫 번째 코드: 각 명령에 대해 최악의 경우 O(n)의 시간이 걸리고, m개의 명령을 처리하면 O(m * n)의 시간이 소요된다.
• 두 번째 코드: 각 명령에 대해 O(1)의 시간이 걸리고, m개의 명령을 처리하면 O(m)의 시간이 소요된다.