🎲 [백준] 5397번. 키로거(Java) feat.stack, LinkedList

문제

https://www.acmicpc.net/problem/5397

 

🎲 문제 해석

문제를 해석하는 것은 물론 굉장히 쉽다. 

우리가 자판을 통해 글씨를 쓸 때 맨 앞에 작성하고 중간에 작성하고 하는것을 생각하면 편하다

다만 특수 문자를 생각해줘야 한다. 우리는 그냥 화살표와 ← 가 그려진 버튼을 누르지만 우리는 그것을 구현하기 위해 받았다는 문자를 '<', '>', '-' 를 통해 받는것이다. 이러한 과정을 거쳤을때 무슨 문자가 남을것이냐가 중요하다

🎲 문제 풀이

사실 문제 풀이가 중요하다.

가장 중요한 것은 커서 포인트의 위치를 어떻게 표현할 것이냐 이다

우선 단순하게 생각해보자

문자를 넣고 빼고 하는 것을 보았을때 대부분 stack을 많이 생각한다. 

그리고 커서가 움직이고 사이에 값을 넣고 빼고 해당 포인트의 뒤에 값을 지운다라고 한다면 LinkedList가 생각난다

---

1. Stack을 사용한 문제 풀이

Stack의 커서 포인트는 바로 2개의 Stack을 두고 그 사이라고 생각하면 된다.

그러면 이제 간단하게 생각하면 된다. 

• '<' : leftStack에 있는 값을 rightStack으로 옮기면 된다
• '>' : rightStack에 있는 값을 leftStack으로 옮기면 된다
• '-' : 커서위치의 왼쪽을 지우기 때문에 leftStack의 가장 위에 있는 값을 지우면 된다.

단순한 예시로 문제의 첫번째 예로 만들었을때 결과는 이렇게 나온다

순서가 역으로 되어있는것을 볼 수 있는데 이것은 rightStack으로 천천히 하나씩 옮기고 그것을 다시 빼면 자연스래 정리가 된다 

코드

    static void stackSolution(char[] charArray) {
        Stack<Character> leftStack = new Stack<>();
        Stack<Character> rightStack = new Stack<>();

        for (char c : charArray) {
            switch (c) {
                case '<' :
                    if (!leftStack.isEmpty()) {
                        rightStack.push(leftStack.pop());
                    }
                    break;
                case '>' :
                    if (!rightStack.isEmpty())
                        leftStack.push(rightStack.pop());
                    break;
                case '-' :
                    if (!leftStack.isEmpty())
                        leftStack.pop();
                    break;
                default:
                    leftStack.push(c);
                    break;
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!leftStack.isEmpty()) {
            rightStack.push(leftStack.pop());
        }

        while (!rightStack.isEmpty()) {
            sb.append(rightStack.pop());
        }
        System.out.println(sb);
    }

---

2. LinkedList를 사용한 문제 풀이 feat.ListIterator

LinkedList는 중간에 값을 넣거나 빼면 숫자가 밀리거나 땡겨지는 것을 활용할 수 있다. 그렇다면 풀이는 굉장히 단순해진다. 하지만 인덱스를 일일히 잡아줘야 한다는 큰 단점이 있는데 이것을 해결하기 위해 ListIterator를 적용하고자 한다

ListIterator란?
List 컬렉션 인터페이스에서 제공하는 인터페이스이다. 이는 리스트를 양방향으로 탐색하고 수정할 수 있는 기능을 제공하게 된다. 이를 통해 해당 문제를 더욱 쉽고 빠르게 가독성마저 고려하며 문제를 풀 수 있다
간단하게 여기서 사용할 메소드를 설명한다
● next() : 리스트의 다음 요소를 반환하고, 커서를 다음 위치로 이동
● previous() : 리스트에서 이전 요소를 반환하고, 커서를 이전 위치로 이동시킨다
● hasNext() : 커서 위치 뒤에 요소가 더 있는지 확인합니다.
● hasPrevious() : 커서 위치 앞에 요소가 더 있는지 확인합니다.
● remove() : 마지막으로 반환된 요소를 리스트에서 제거합니다.

그렇다면 이제 각각 특수 문자에 어떤 메소드를 사용하면 좋을까?

• '<' : hasPrevious를 통해 이전의 값이 있다면 previous로 커서를 이동 (반환은 하지만 필요는 없다)
• '>' : hasNext를 통해 다음 요소의 존재를 확인하고 있다면 next로 커서를 이동한다(반환은 하지만 필요는 없다)
• '-' : remove를 하면 되는데 hasprevious를 통해 이전의 값이 있는지 확인해야하고 이동하고 지우면 된다.

💥 주의점은 마지막 값을 지울때 이동을 먼저 하고 지워야 한다는 것이다.

지우고 이동하면 IllegalStateException이 발생한다. 왜냐하면  listIterator에서 remove는 호출 조건이 있다. 바로 next 혹은 previous를 호출해야 한다는 것이다. 왜냐하면 listIterator가 현재 커서의 위치를 전달 받기 위해서이다. 바로 remove를 호출한다면 listIterator는 어떤 요소를 삭제해야 하는지 알 수 없다.

 

코드

    static void linkListSolution(char[] charArray) {
        List<Character> list = new LinkedList<>();
        ListIterator<Character> iterList = list.listIterator();

        for (char c : charArray) {
            switch (c) {
                case '<':
                    if (iterList.hasPrevious()) {
                        iterList.previous();
                    }
                    break;
                case '>':
                    if (iterList.hasNext()) {
                        iterList.next();
                    }
                    break;
                case '-':
                    if (iterList.hasPrevious()) {
                        iterList.previous();
                        iterList.remove();
                    }
                    break;
                default:
                    iterList.add(c);
                    break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Character c : list) {
            sb.append(c);
        }
        System.out.println(sb);
    }

 

시간 복잡도

2개의 문제 풀이를 봤는데 둘 다 정답이다 그렇다면 어떤 방식을 쓰는게 더 좋을까??

일단 시간 복잡도 자체는 코드를 보면 대충 감이 오겠지만 둘 다 문자열 전체를 한 번 검색한다

그렇기에 동일한 O(n)을 가지고 있다. 

 

그래서 사실 이중에 내가 더 빠르고 쉽게 생각하기 좋은 방법으로 구현하는 것이 좋을거같다

 

하지만 공간 복잡도까지 걸고 간다면 

2번의 풀이인 경우 LinkedList를 한개만 사용하지만 1번의 풀이는 Stack 공간을 2개를 확보해야하기 때문에 좀 더 안좋다고 볼수 있다.