자바 - Deque의 LinkedList로 코테 푸는 법

LinkedList는 List, Queue, Deque을 다 implements 한다.

다른 인터페이스로 구현된 LinkedList는 다른 글에서 볼 수 있고

여기서는 Deque으로 구현된 것만 확인한다.

 

그 전에...

Deque의 LinkedList를 사용해야 하는 문제 유형

Deque의 LinkedList 구현은 특히 다음과 같은 유형의 문제 해결에 적합합니다:

• 양방향 큐 구현: 문제가 데이터의 양 끝에서 추가 및 삭제를 자주 요구할 때, 예를 들어 스택이나 큐의 기능이 결합된 형태가 필요한 경우.
• 양방향 순회가 필요한 경우: 데이터를 앞뒤로 자유롭게 탐색해야 할 때 유리합니다.
• 실시간 계산 문제: 데이터의 앞부분이나 뒷부분에서 요소를 추가하거나 제거하면서 실시간으로 최대값, 최소값 등을 계산해야 하는 문제.
• 슬라이딩 윈도우: 데이터의 연속적인 구간(윈도우)에서 최소값, 최대값 등을 빠르게 업데이트하면서 처리해야 하는 문제. Deque를 사용하면 윈도우 내의 데이터를 효율적으로 관리할 수 있습니다.
• BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색): 탐색 알고리즘에서 Deque를 사용하면 큐와 스택의 기능을 동시에 활용할 수 있어, BFS와 DFS를 효율적으로 구현할 수 있습니다.

Deque의 LinkedList는 그 유연성과 다재다능함으로 인해 다양한 상황에서 유용하게 사용될 수 있으며, 특히 양쪽 끝에서의 작업이 빈번하게 요구되는 문제에서 강점을 발휘합니다.

 

그리고 GPT한테 덱의 링크드리스트를 쓰기 좋은 문제를 만들어 달라고 하니까 Stack에서 썼던 팰린드롬 문제를 또 만들더라.

'이걸 정말 하는 게 맞나?' 고민했는데...

팰린드롬을 Deque의 LinkedList로 처리하는 이유

팰린드롬 문제를 스택을 사용하여 처리하는 것이 가능하지만, Deque의 LinkedList를 사용하는 것은 다음과 같은 이점을 제공합니다:

• 양방향 접근 용이성: Deque 인터페이스를 통해 제공되는 addFirst, addLast, removeFirst, removeLast와 같은 메서드들은 문자열의 앞과 뒤에서 요소를 추가하거나 제거하는 데 최적화되어 있습니다. 이를 통해 팰린드롬 검사 시에 시작과 끝 문자를 쉽게 비교하고 제거할 수 있습니다.
• 메모리 및 성능 최적화: Deque의 LinkedList 구현은 동적으로 요소를 추가하고 삭제할 수 있으며, 인덱스를 참조하지 않고 직접 노드를 추가하거나 제거하기 때문에 불필요한 메모리 할당과 재할당을 줄일 수 있습니다. 이는 특히 문자열이 길어질 경우 유리할 수 있습니다.
• 단순성과 직관성: Deque를 사용하면 코드가 좀 더 읽기 쉽고 이해하기 쉬워집니다. 앞뒤로 삽입하고 삭제하는 로직을 명확하게 표현할 수 있습니다.

둘의 코드 진행을 비교하는 것도 괜찮을 것 같아 그대로 진행한다.

문제: 팰린드롬 문자열 검사

문제 설명: 주어진 문자열이 팰린드롬인지 확인합니다. 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 동일한 문자열을 의미합니다. 대소문자를 구분하지 않으며, 문자와 숫자만을 대상으로 합니다.

 

예시:

• 입력: "A man, a plan, a canal: Panama"
• 출력: true

예시:

• 입력: "race a car"
• 출력: false

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public boolean isPalindrome(String s) {
        s = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        Deque<Character> deque = new LinkedList<>();

        for (char ch : s.toCharArray()) {
            deque.offerLast(ch);
        }

        while (deque.size() > 1) {
            if (deque.pollFirst() != deque.pollLast()) {
                return false;
            }
        }

        return true;
    }
}

 

'오..! 이게 더 쉬운데?'싶어 스택 문풀 포스트를 보니...

팰린드롬이 아니고 괄호 비교 문제였고요...

'그럼 내가 전에 풀었던 팰린드롬 문제는 뭐였지?'하고 돌이켜 보니...

내가 날려 먹은 List의 LinkedList에서 이 문제를 했었군...

 

팰린드롬 문제를 스택을 사용해서 푸는 방법은 가능하지만, 일반적으로 가장 효율적이거나 권장되는 방법은 아닙니다. 스택을 사용한 접근 방법은 주로 문자열의 절반을 스택에 넣고, 나머지 절반과 비교하여 팰린드롬 여부를 판단하는 방식으로 진행됩니다. 그러나 이 방법은 일반적으로 두 포인터(Two Pointers) 접근법이나 데크(Deque)를 사용하는 방법에 비해 더 복잡하거나 비효율적일 수 있습니다.

스택을 사용하는 방법

스택을 사용하여 팰린드롬을 검사하는 과정은 다음과 같습니다:

1. 문자열 절반 삽입: 문자열의 첫 번째 절반을 스택에 삽입합니다.
2. 중간 점 확인: 문자열의 길이가 홀수인 경우 중간 요소는 무시하고 진행합니다.
3. 스택 비교: 문자열의 나머지 절반을 스택의 상단 요소와 비교하면서 팝(pop) 연산을 수행합니다. 모든 문자가 일치해야 팰린드롬입니다.

스택 사용의 한계

• 메모리 사용: 스택을 사용하면 문자열의 절반을 저장하기 위한 추가 메모리가 필요합니다.
• 효율성: 문자열을 두 번 순회해야 하며 (한 번은 스택에 넣고, 한 번은 스택에서 빼면서 비교), 추가적인 스택 연산이 필요합니다.

더 간단한 방법: 두 포인터 기법

팰린드롬을 검사하는 더 효율적인 방법은 두 포인터를 사용하는 것입니다:

1. 두 포인터 초기화: 한 포인터는 문자열의 시작에, 다른 하나는 끝에 위치시킵니다.
2. 비교 및 이동: 두 포인터가 가리키는 문자를 비교하고, 문자들이 같다면 포인터를 서로 가운데로 이동시킵니다.
3. 검증: 모든 문자가 일치하면 문자열은 팰린드롬입니다.

이 방법은 추가 메모리를 필요로 하지 않으며, 문자열을 한 번만 순회하면 되므로 시간과 공간 효율성 모두에서 우수합니다.

결론

팰린드롬을 검사하기 위해 스택을 사용할 수는 있지만, 더 간단하고 효율적인 방법이 있습니다. 문제의 요구사항과 사용 가능한 자원, 그리고 구현의 복잡성을 고려하여 가장 적합한 방법을 선택하는 것이 좋습니다.

 

자~ 이제 ArrayDeque 보러 갑시다!