알고리즘 스터디 2주차 - 3

1406

• 알고리즘 : 스택, 연결리스트
• 난이도 : 실버2

문제

1406

접근

• StringBuilder의 메서드를 적절히 활용하면 되겠다.
• 커서의 위치를 index로 활용한다.
  • index가 0이거나 현재 문자열의 크기와 같을 경우 L,B 또는 D를 무시
• 추가할 때 insert문으로 추가

가정

• StringBuilder로 작성할 수 있다.
• 커서의 위치를 추적한다.

풀어보기

package org.example;

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

public class Main {
	public static void main(String[] args) throws IOException {
		// L : 커서를 왼쪽으로 한칸 옮김
		// D : 커서를 오른쪽으로 한칸 옮김
		// B : 커서 왼쪽의 문자를 삭제함
		// P & : &문자를 커서 왼쪽에 추가함
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String init = reader.readLine();
		int commandCount = Integer.parseInt(reader.readLine());

		LinkedList<Character> list = new LinkedList<>();
		for(char c : init.toCharArray()) {
			list.add(c);
		}

		//Iterator로 커서의 위치를 관리
		ListIterator<Character> listIterator = list.listIterator();
		while(listIterator.hasNext()) {
			listIterator.next();
		} // 커서를 끝으로 보냄

		for(int i = 0; i< commandCount; i++) {
			String [] command = reader.readLine().split(" ");
			if(command[0].equals("P")) {
				listIterator.add(command[1].charAt(0));
				continue;
			}
			if(command[0].equals("L")) {
				if(listIterator.hasPrevious()) {

                listIterator.previous();
				}
				continue;
			}
			if(command[0].equals("D")) {
				if(listIterator.hasNext()){
					listIterator.next();
				}
				continue;
			}
			if(command[0].equals("B")) {
				if(listIterator.hasPrevious()){
					listIterator.previous();
					listIterator.remove();
				}
			}
		}

		StringBuilder result = new StringBuilder();
		for(char c : list) {
			result.append(c);
		}
		System.out.println(result.toString());
	}
}

시행착오

• 문자열을 직접 관리해서 시간초과가 발생한다.
• linkedlist를 활용하여 다음 문자의 연결을 주소로 관리하여 시간초과를 해결한다.

참고자료

• 시간초과 나는 이유