[알고리즘] 백준 - 키로거

June·2021년 6월 2일
0

알고리즘

목록 보기
217/260

백준 - 키로거

내 풀이 (스택)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


public class baekjoon_5397 {

    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int k = 0; k < N; k++) {
            Stack<Character> stack1 = new Stack<>();
            Stack<Character> stack2 = new Stack<>();
            String input = br.readLine();

            for (int i = 0; i < input.length(); i++) {
                if (input.charAt(i) == '<') {
                    if (!stack1.isEmpty()) {
                        stack2.add(stack1.pop());
                    }
                } else if (input.charAt(i) == '>') {
                    if (!stack2.isEmpty()) {
                        stack1.add(stack2.pop());
                    }
                } else if (input.charAt(i) == '-') {
                    if (!stack1.isEmpty()) {
                        stack1.pop();
                    }
                } else {
                    stack1.add(input.charAt(i));
                }
            }

            StringBuffer answer = new StringBuffer();
            StringBuffer string1 = new StringBuffer();
            while (!stack1.isEmpty()) {
                string1.append(stack1.pop());
            }
            answer = string1.reverse();
            string1 = new StringBuffer();
            while (!stack2.isEmpty()) {
                string1.append(stack2.pop());
            }
            answer.append(string1);
            System.out.println(answer);
        }
    }
}

예전 백준 에디터 문제 비슷하게 풀었다. 처음 풀었을 때 통과하지 못했는데, 앞에 스택은 팝해서 모은다음 거꾸로 해줘야하고, 뒤에 스택은 팝만 하면 된다.

다른 사람 풀이 (더블리 링크드 리스트)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
 
public class Main {
    static LinkedList<Character> lnklist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int TC = Integer.parseInt(br.readLine());
        for(int i = 0; i < TC; i++) {
            lnklist = new LinkedList<>();
            ListIterator<Character> list = lnklist.listIterator();
            String str = br.readLine();
            
            for(int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                switch(c) {
                    case '<' :
                        if(list.hasPrevious()) {
                            list.previous();
                        }
                        break;
                    case '>' :
                        if(list.hasNext()) {
                            list.next();
                        }
                        break;
                    case '-' :
                        if(list.hasPrevious()) {
                            list.previous();
                            list.remove();
                        }
                        break;
                    default : 
                        list.add(c);
                }
            }
            
            StringBuilder sb = new StringBuilder();
            for(char s : lnklist) {
                sb.append(s);
            }
            System.out.println(sb.toString());
        }
    }
}

https://godzz.tistory.com/11

개념

String vs StringBuilder vs SringBuffer

https://ifuwanna.tistory.com/221

| String vs StringBuffer/StringBuilder

String과 StringBuffer/StringBuilder 클래스의 가장 큰 차이점은 String은 불변(immutable)의 속성을 갖는다는 점입니다.

String str = "hello"; // String str = new String("hello"); 
str = str + " world"; // [ hello world ]

직관적이어서 가장 많이 사용할 듯한 위의 예제에서 "hello" 값을 가지고 있던 String 클래스의 참조변수 str이 가리키는 곳에 저장된 "hello"에 "world" 문자열을 더해 "hello world"로 변경한 것으로 착각할 수 있습니다.

하지만 기존에 "hello" 값이 들어가있던 String 클래스의 참조변수 str이 "hello world"라는 값을 가지고 있는 새로운 메모리영역을 가리키게 변경되고 처음 선언했던 "hello"로 값이 할당되어 있던 메모리 영역은 Garbage로 남아있다가 GC(garbage collection)에 의해 사라지게 되는 것 입니다. String 클래스는 불변하기 때문에 문자열을 수정하는 시점에 새로운 String 인스턴스가 생성된 것이지요.

위와 같이 String은 불변성을 가지기 때문에 변하지 않는 문자열을 자주 읽어들이는 경우 String을 사용해 주시면 좋은 성능을 기대할 수 있습니다. 그러나 문자열 추가,수정,삭제 등의 연산이 빈번하게 발생하는 알고리즘에 String 클래스를 사용하면 힙 메모리(Heap)에 많은 임시 가비지(Garbage)가 생성되어 힙메모리가 부족으로 어플리케이션 성능에 치명적인 영향을 끼치게 됩니다.

이를 해결하기 위해 Java에서는 가변(mutable)성을 가지는 StringBuffer / StringBuilder 클래스를 도입했습니다.
String 과는 반대로 StringBuffer/StringBuilder 는 가변성 가지기 때문에 .append() .delete() 등의 API를 이용하여 동일 객체내에서 문자열을 변경하는 것이 가능합니다. 따라서 문자열의 추가,수정,삭제가 빈번하게 발생할 경우라면 String 클래스가 아닌 StringBuffer/StringBuilder를 사용하셔야 합니다.

StringBuffer vs StringBuilder

가장 큰 차이점은 동기화의 유무로써 StringBuffer는 동기화 키워드를 지원하여 멀티쓰레드 환경에서 안전하다는 점(thread-safe) 입니다. 참고로 String도 불변성을 가지기때문에 마찬가지로 멀티쓰레드 환경에서의 안정성(thread-safe)을 가지고 있습니다.

StringBuilder는 동기화를 지원하지 않기때문에 멀티쓰레드 환경에서 사용하는 것은 적합하지 않지만 동기화를 고려하지 않는 만큼 단일쓰레드에서의 성능은 StringBuffer 보다 뛰어납니다.

0개의 댓글