[백준] 스택 - 1406

1.중간에 삽입 시에 현재커서 뒷부분을 모두 스택에 옮기기 + 실제 sb에서도 삭제하기, 삽입이 끝나면 스택에 있던 데이터를 모두 sb에 더해줌

>> 시간초과.

package BackJun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Stack_Q1406 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		String str = br.readLine();
		Stack<Character> stack = new Stack<Character>();
		
		sb.append(str); //sb에 str 넣어주기
		
		int max_cursor = str.length();
		int now_cursor = max_cursor;
		
		int M = Integer.parseInt(br.readLine());
		for(int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			String order = st.nextToken();
			
			switch(order) {
			case "L": //커서 왼쪽으로 옮기기
				if(now_cursor != 0)
					now_cursor--;
				break;
			case "D": //커서 오른쪽으로 옮기기
				if(now_cursor != max_cursor)
					now_cursor++;
				break;
			case "B": //커서 왼쪽문자 삭제
				if(now_cursor != 0) {
					sb.deleteCharAt(now_cursor - 1);
					max_cursor--;
					now_cursor--;
				}
				break;
			case "P": //커서 왼쪽에 해당 문자열 추가
				String plus = st.nextToken();
				int deleteNum = max_cursor - now_cursor;
				for(int i = deleteNum; i > 0; i--) {
					stack.push(sb.charAt(i - 1)); //스택에 담아주고
					sb.deleteCharAt(i - 1);//삭제
				}
				sb.append(plus);//문자열 추가
				max_cursor++;
				now_cursor++;
				for(int i = 0; i < deleteNum; i++) {
					sb.append(stack.pop());//스택에 있던 것들 다시 추가
				}
				break;
			}
		}
		System.out.print(sb);

	}

}

 

2. 스택을 2개 사용 (성공)

커서가 이동하는 방향대로 한 곳에선 pop 한 곳에선 push

메모리 : 143760 KB

시간 : 712 ms

코드길이 : 1572 B

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		String str = br.readLine();
		Stack<Character> leftStack = new Stack<Character>();
		Stack<Character> rightStack = new Stack<Character>();
		
		for(int i = 0; i < str.length(); i++) {
			leftStack.push(str.charAt(i));
		}
		
		int M = Integer.parseInt(br.readLine());
		for(int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			String order = st.nextToken();
			
			switch(order) {
			case "L": //커서 왼쪽으로 옮기기
				if(!leftStack.isEmpty()) //왼스택이 비어있지 않을 때
					rightStack.push(leftStack.pop());
				break;
			case "D": //커서 오른쪽으로 옮기기
				if(!rightStack.isEmpty()) //오른스택이 비어있지 않을 때
					leftStack.push(rightStack.pop());
				break;
			case "B": //커서 왼쪽문자 삭제
				if(!leftStack.isEmpty()) //왼스택이 비어있지 않을 때
					leftStack.pop();
				break;
			case "P": //커서 왼쪽에 해당 문자열 추가
				String plus = st.nextToken();
				leftStack.push(plus.charAt(0));
				break;
			}
		}
		while(!leftStack.isEmpty()) { //pop할 때 정방향으로 나오려면 rightStack에서 빼내야 하기 때문에 옮겨줌
			rightStack.push(leftStack.pop());
		}
		while(!rightStack.isEmpty()) {
			sb.append(rightStack.pop());
		}
		System.out.print(sb);

	}

}

 

1등 코드

메모리 : 21480 KB

시간 : 132 ms

코드길이 : 3281 B

[상위권 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Main.MaroReader mr = new MaroReader(65536, 100001, true);
        Main.MaroWriter mw = new MaroWriter(65536);
        Deque<Byte> l = new ArrayDeque<>();
        Deque<Byte> r = new ArrayDeque<>();
        for(byte b : mr.nextBytes()) {
            if(b == 0) break;
            l.add(b);
        }
        int n = mr.nextInt();
        for(int i=0; i<n; i++) {
            byte b = mr.read();
            switch(b) {
                case 'L':
                    if(!l.isEmpty()) r.addLast(l.removeLast());
                    break;
                case 'D':
                    if(!r.isEmpty()) l.addLast(r.removeLast());
                    break;
                case 'B':
                    if(!l.isEmpty()) l.removeLast();
                    break;
                case 'P':
                    mr.read();
                    l.addLast(mr.read());
                    break;
            }
            if(i!=n-1) mr.read();
        }
        while(!l.isEmpty()) mw.write(l.removeFirst());
        while(!r.isEmpty()) mw.write(r.removeLast());
        mw.flush();
    }
    // Main 하단에 고정.
    public static class MaroReader {
        private final InputStream in = System.in;
        private final byte[] b;
        private final boolean isNatural;
        private final int sz;
        private final int strMax;
        private int s, idx, rCnt;
        public MaroReader(int sz, int max, boolean isNatural) {
            this.b = new byte[this.sz=sz];
            this.strMax = max;
            this.isNatural = isNatural;
        }
        private void refill() throws IOException {
            rCnt = in.read(b, idx=0, sz);
            if(rCnt<0) b[0] = -1;
        }
        private byte read() throws IOException {
            if(idx >= rCnt) refill(); return b[idx++];
        }
        public int nextInt() throws IOException {
            int a;
            byte b=read();
            if(isNatural) {
                a=b-'0';
                while((b=read())>='0' && b<='9') a=a*10+b-'0';
                return a;
            } else {
                boolean isNeg = b=='-';
                if(isNeg) b=read();
                a=b-'0';
                while((b=read())>='0' && b<='9') a=a*10+b-'0';
                return isNeg?-a:a;
            }
        }
        public byte[] nextBytes() throws IOException {
            byte[] str = new byte[strMax];
            s = 0;
            byte b = read();
            if(b == -1) return null;
            str[s++]=b;
            while((b=read())>' ' && b<0x7F) str[s++]=b;
            return str;
        }
        public String nextString() throws IOException {
            StringBuilder sb = new StringBuilder();
            byte b = read();
            if(b == -1) return null;
            do sb.append((char)b);
            while((b=read())>' ' && b<0x7F);
            return sb.toString();
        }
        public int getS() {
            return s;
        }
    }
    public static class MaroWriter {
        private final OutputStream out = System.out;
        private final byte[] b;
        private final int sz;
        private int bufferIdx;
        MaroWriter(int sz) { this.b = new byte[this.sz=sz]; }
        public void write(byte b) throws IOException {
            if(bufferIdx == sz) flushBuffer(); this.b[bufferIdx++] = b;
        }
        public void write(int i) throws IOException {
            byte[] tmp = new byte[11];
            int idx = 0;
            boolean isNeg = i<0;
            if(i==0) tmp[idx++] = '0';
            else while(i!=0) {
                int t=i%10;
                tmp[idx++] = (byte)('0'+(t<0?-t:t));
                i/=10;
            }
            if(isNeg) tmp[idx++] = '-';
            for(int j=idx-1; j>=0; j--) write(tmp[j]);
        }
        public void write(long l) throws IOException {
            byte[] tmp = new byte[20];
            int idx = 0;
            boolean isNeg = l<0;
            if(l==0) tmp[idx++] = '0';
            else while(l!=0) {
                long t=l%10;
                tmp[idx++] = (byte)('0'+(t<0?-t:t));
                l/=10;
            }
            if(isNeg) tmp[idx++] = '-';
            for(int j=idx-1; j>=0; j--) write(tmp[j]);
        }
        public void write(String s) throws IOException {
            byte[] str = s.getBytes();
            write(str, str.length);
        }
        public void write(byte[] str, int length) throws IOException{
            for(int i=0; i<length; i++) write(str[i]);
        }
        public void flush() throws IOException { if(bufferIdx > 0) flushBuffer(); out.flush(); }
        private void flushBuffer() throws IOException { out.write(b, 0, bufferIdx); bufferIdx = 0; }
        public void newLine() throws IOException{ write((byte)'\n'); }
        public void space() throws IOException{ write((byte)' '); }
    }
}

ListIterator 사용하는 방법도 있음