곽로그
[백준 1406, Java] 에디터 본문
반응형
문제
1406번: 에디터
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수
www.acmicpc.net
check
1. 배열을 이용한 풀이에서 시간 초과가 나는이유
- 배열을 이용하게 되면 수정과 삭제를 할때 배열의 최악의 경우 길이만큼의 시간이 필요하다. (맨 앞요소를 삭제하는 경우, 인덱스 1부터 N-1까지를 0부터 N-2 까지 옮겨야 한다)
- 문제의 최대 입력(N)은 100,000 이고 수행 명령(M)은 최대 500,000이다.
- 따라서 시간 복잡도는 NM = 50,000,000,000 500억인데 1억이 1초라고 가정한다면 시간초과가 날 수 밖에 없다.
2. 링크드리스트
배열은 수정과 삭제에서 N 만큼의 시간이 들지만 링크드 리스트는 1이므로 두번째 풀이는 링크드 리스트를 이용해서 풀었다. 근데도 시간초과가 났다.
3. 스택
스택을 이용한 풀이는 생각을 하지 못했다. 백준 강의를 듣고서야 풀 수 있었다.
- 스택의 특성 : 맨 위에 있는 요소가 가장 마지막에 입력된 요소 = 가장 최근에 입력된 요소 = 기준에서 가장 가까운 요소
소스코드
1. 배열을 이용한 풀이( 시간초과)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
String line = br.readLine().trim();
Editor editor = new Editor(line);
int N = Integer.parseInt(br.readLine().trim());
for(int n = 0 ; n<N ; n++){
st = new StringTokenizer(br.readLine()," ");
String command = st.nextToken();
if(command.equals("L")){
editor.commandL();
}
else if(command.equals("D")){
editor.commandD();
}
else if(command.equals("B")){
editor.commandB();
}
else if (command.equals("P")){
char x = st.nextToken().charAt(0);
editor.commandP(x);
}
}
editor.printArray();
}
}
class Editor{
char[] characterLine;
int length;
int pointer;
int charCount;
Editor (String line){
characterLine = new char[20000000];
for(int index = 0; index<line.length();index++){
characterLine[index] = line.charAt(index);
}
pointer = line.length();
charCount = line.length();
}
/* 문자를 커서 자리에 추가 */
// 커서자리가 문자의 끝이면 커서 자리에 문자 추가
// 아닌 경우는 한칸씩 뒤로 미루기
public void commandP(char x){
for(int index = charCount-1; index>=pointer; index--){
characterLine[index+1] = characterLine[index];
}
characterLine[pointer] = x;
++charCount;
++pointer;
}
/* 왼쪽문자 삭제 */
// charCount까지 복사해 오면 마지막 문자를 삭제할 필요가 없다
public void commandB(){
if(pointer!=0){
for(int index = pointer ; index <= charCount; index++){
characterLine[index-1] = characterLine[index];
}
--charCount;
--pointer;
}
}
public void commandL(){
if(pointer!=0){
--pointer;
}
}
public void commandD(){
if(pointer != charCount){
++pointer;
}
}
public void printArray(){
for(int index = 0; index<charCount; index++){
System.out.print(characterLine[index]);
}
System.out.println();
}
}
2. 스택을 이용한 풀이
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
String line;
String command;
line = br.readLine().trim();
int M = Integer.parseInt(br.readLine());
//초기화 작업
Stack<Character> cursorLeft = new Stack<>();
Stack<Character> cursorRight = new Stack<>();
for(int index = 0 ; index<line.length() ; index++){
cursorLeft.push(line.charAt(index));
}
for(int m = 0; m<M; m++ ){
st = new StringTokenizer(br.readLine()," ");
command = st.nextToken();
if (command.equals("L")){
//커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
if(!cursorLeft.isEmpty()){
cursorRight.push(cursorLeft.pop());
}
}
else if(command.equals("D")){
//커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
if(!cursorRight.isEmpty()){
cursorLeft.push(cursorRight.pop());
}
}
else if(command.equals("B")){
//커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
if(!cursorLeft.isEmpty()){
cursorLeft.pop();
}
}
else if(command.equals("P")){
//$라는 문자를 커서 왼쪽에 추가함
char alphabet = st.nextToken().charAt(0);
cursorLeft.push(alphabet);
}
}
while(!cursorLeft.isEmpty()){
cursorRight.push(cursorLeft.pop());
}
while (!cursorRight.isEmpty()){
bw.write(cursorRight.pop());
}
bw.flush();
}
}
2021.01.04 - 2번코드 case문으로 정리
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static Stack<String> leftStack;
public static Stack<String> rightStack;
public static int M;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
String[] line = br.readLine().split("");
M = Integer.parseInt(br.readLine());
leftStack = new Stack<>();
rightStack = new Stack<>();
for(int index = 0; index<line.length;index++){
leftStack.push(line[index]);
}
for(int count = 0 ; count<M; count++){
st = new StringTokenizer(br.readLine()," ");
String command = st.nextToken();
switch (command){
case "L":
commandL();
break;
case "D":
commandD();
break;
case "B" :
commandB();
break;
case "P":
String alphabet = st.nextToken();
commandP(alphabet);
break;
}
}
String result = print();
bw.write(result);
bw.flush();
}
public static void commandL(){
//커서를 왼쪽으로
if(!leftStack.isEmpty()){
rightStack.push(leftStack.pop());
}
}
public static void commandD(){
//커서를 오른쪽으로
if(!rightStack.isEmpty()){
leftStack.push(rightStack.pop());
}
}
public static void commandB(){
//커서 왼쪽에 있는 문자를 삭제
if(!leftStack.isEmpty()){
leftStack.pop();
}
}
public static void commandP(String alphabet){
leftStack.push(alphabet);
}
public static String print(){
StringBuffer result = new StringBuffer();
while (!leftStack.isEmpty()){
rightStack.push(leftStack.pop());
}
while(!rightStack.isEmpty()){
result.append(rightStack.pop());
}
return result.toString();
}
}
3. LinkedList를 이용한 풀이
- 그냥 풀면 시간초과
- ListIterator를 사용해야함.
- 이때 출력을 그냥 for문으로 하면 시간초과남
- enhanced for문으로 해야함
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;
public class Main {
public static LinkedList<Character> linkedList;
public static int cursor = 0;
public static int N;
public static int M;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
String word ;
String command;
Character alphabet;
word = br.readLine();
linkedList = new LinkedList<>();
for(int index = 0 ; index<word.length(); index++){
linkedList.add(word.charAt(index));
}
ListIterator<Character> iter = linkedList.listIterator();
while(iter.hasNext()){
iter.next();
}
M = Integer.parseInt(br.readLine());
for(int count = 0; count<M; count++){
command = br.readLine();
switch (command.charAt(0)){
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':
alphabet = command.charAt(2);
iter.add(alphabet);
break;
}
}
for(Character c : linkedList){
bw.write(c);
}
bw.flush();
bw.close();
}
}
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 10799, Java] 쇠막대기 (0) | 2020.10.28 |
|---|---|
| [백준 17413, Java] 단어 뒤집기2 (0) | 2020.10.28 |
| [백준 10820, Java] 문자열 분석 (0) | 2020.10.27 |
| [백준 1935, Java] 후위표기식2 (0) | 2020.10.26 |
| [백준1158, Java] 요세푸스 문제 (0) | 2020.10.20 |
Comments