백준 - 키로거 (실버 2)

시간초과 발생

 

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

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));
        int N=Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            String[] s=br.readLine().split("");
            List <String> list=new LinkedList<>();
            ListIterator <String> iter=list.listIterator();
            for(int j=0;j<s.length;j++){
                String str=s[j];
                switch(str){
                    case "<":
                        if(iter.hasPrevious())
                            iter.previous();
                        break;
                    case ">":
                        if(iter.hasNext())
                            iter.next();
                        break;
                    case "-":
                        if(iter.hasPrevious()){
                            iter.previous();
                            iter.remove();
                        }
                        break;
                    default:
                        iter.add(str);
                }
            }
            StringBuilder sb=new StringBuilder();
            for(int j=0;j<list.size();j++){
                sb.append(list.get(j));
            }
            sb.append("\n");
            bw.write(sb.toString());
        }
        bw.flush();
        bw.close();
    }
}

 

---

 

join() 함수로 바꿔서 출력하니  성공

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

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));
        int N=Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            String[] s=br.readLine().split("");
            List <String> list=new LinkedList<>();
            ListIterator <String> iter=list.listIterator();
            for(int j=0;j<s.length;j++){
                String str=s[j];
                switch(str){
                    case "<":
                        if(iter.hasPrevious())
                            iter.previous();
                        break;
                    case ">":
                        if(iter.hasNext())
                            iter.next();
                        break;
                    case "-":
                        if(iter.hasPrevious()){
                            iter.previous();
                            iter.remove();
                        }
                        break;
                    default:
                        iter.add(str);
                }
            }
            
            bw.write(String.join("",list)+"\n");
        }
        bw.flush();
        bw.close();
    }
}

 

---

stack을 이용한 풀이

 

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

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));
        int N=Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            String[] s=br.readLine().split("");
            Stack <String> left_stack=new Stack<>();
            Stack <String> right_stack=new Stack<>();

            for(int j=0;j<s.length;j++){
                String str=s[j];
                switch(str){
                    case "<":
                        if(!left_stack.isEmpty())
                            right_stack.push(left_stack.pop());
                        break;
                    case ">":
                        if(!right_stack.isEmpty())
                            left_stack.push(right_stack.pop());
                        break;
                    case "-":
                        if(!left_stack.isEmpty()){
                            left_stack.pop();
                        }
                        break;
                    default:
                        left_stack.push(str);
                }
            }
            while(!left_stack.isEmpty()){
                right_stack.push(left_stack.pop());
            }
            while(!right_stack.isEmpty()){
                bw.write(right_stack.pop());
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
}

 

 

Char로 다루니깐 실행시간이 반이상 줄었다.

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

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));
        int N=Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            String s=br.readLine();
            Stack <Character> left_stack=new Stack<>();
            Stack <Character> right_stack=new Stack<>();

            for(int j=0;j<s.length();j++){
                char ch=s.charAt(j);
                switch(ch){
                    case '<':
                        if(!left_stack.isEmpty())
                            right_stack.push(left_stack.pop());
                        break;
                    case '>':
                        if(!right_stack.isEmpty())
                            left_stack.push(right_stack.pop());
                        break;
                    case '-':
                        if(!left_stack.isEmpty()){
                            left_stack.pop();
                        }
                        break;
                    default:
                        left_stack.push(ch);
                }
            }
            while(!left_stack.isEmpty()){
                right_stack.push(left_stack.pop());
            }
            while(!right_stack.isEmpty()){
                bw.write(right_stack.pop());
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
}

 

 

 

ListIterator도 char로 바꾸니 마찬가지로 줄었다.

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

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));
        int N=Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            String s=br.readLine();
            List <Character> list=new LinkedList<>();
            ListIterator <Character> iter=list.listIterator();
            for(int j=0;j<s.length();j++){
                char ch=s.charAt(j);
                switch(ch){
                    case '<':
                        if(iter.hasPrevious())
                            iter.previous();
                        break;
                    case '>':
                        if(iter.hasNext())
                            iter.next();
                        break;
                    case '-':
                        if(iter.hasPrevious()){
                            iter.previous();
                            iter.remove();
                        }
                        break;
                    default:
                        iter.add(ch);
                }
            }
            StringBuilder sb=new StringBuilder();
            for(char c:list){
                sb.append(c);
            }
            bw.write(sb.toString()+"\n");
        }
        bw.flush();
        bw.close();
    }
}

 

 

다만, 출력할 때 다음과 같이 향상된 for문으로 list의 원소를 하나씩 꺼내와야 시간초과가 안 뜬다.

get() 함수로 하나씩 꺼내왔더니 시간초과가 발생했다.

-> get() 함수로 원소 하나당 시간복잡도가 O(n)이기 때문. 총 n^2번 걸림.

-> 향상된 for문은 원소 하나당 시간복잡도가 O(1)이므로 총 n번 걸림.

 

StringBuilder sb=new StringBuilder();
            for(char c:list){
                sb.append(c);
            }
            bw.write(sb.toString()+"\n");