[Hackerrank 문제 풀이] Queues and Stacks

Junu Kim·2025년 11월 21일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

43/46

[Queue&Stack] Queues and Stacks

난이도: ★☆☆☆☆ • solved on: 2025-11-21

문제 요약

문제 유형: 자료구조(Queue, Stack), 문자열 검사
요구사항:
주어진 문자열이 palindrome(회문)인지 확인하기 위해
Stack에는 앞에서부터 문자 push, Queue에는 뒤에서부터 문자 enqueue 하여
pop/dequeue 결과가 동일한지 검사한다.

사용 개념

자료구조
- Stack: LIFO 구조를 적용하기 위해 ArrayDeque의 push/pop 사용
- Queue: FIFO 구조를 위해 ArrayDeque의 add/poll 사용
알고리즘/기법
- 투 포인터 대신 스택과 큐의 대조 방식 사용
- 문자열 순회 후 스택 pop과 큐 poll 결과 비교
핵심 키워드
- LIFO, FIFO
- 자료구조 구현
- palindrome 검사

풀이 아이디어

문제 분해

문자열의 각 문자를 stack과 queue에 각각 push/enqueue 한다.

stack은 뒤에서부터, queue는 앞에서부터 문자를 꺼내므로
두 자료구조에서 나온 문자를 매번 비교하면 palindrome 여부를 판단할 수 있다.
핵심 로직 흐름
for each char in s:
    pushCharacter(c)    // stack.push
    enqueueCharacter(c) // queue.add

repeat n/2:
    if popCharacter() != dequeueCharacter():
        not palindrome
예외 처리

문자열 길이가 1 또는 0인 경우 무조건 palindrome 처리 (하지만 이번 문제에서는 생각할 필요가 없었다)

코드

public class Solution {
    // Write your code here.
    public Deque<Character> stack;
    public Queue<Character> queue;
    
    public Solution(){
        this.stack = new ArrayDeque<>();
        this.queue = new ArrayDeque<>();
    }
    
    public void pushCharacter(char ch){
        stack.push(ch);
    }
    public void enqueueCharacter(char ch){
        queue.add(ch);
    }
    public char popCharacter(){
        return stack.pop();
    }
    
    public char dequeueCharacter(){
        return queue.poll();
    }
}

시간·공간 복잡도 (실제 문제에서는 고려할 필요 X)

시간 복잡도: O(N)
(한 번은 push/enqueue, 한 번은 pop/dequeue 순회)
공간 복잡도: O(N)
(stack과 queue에 N개 문자 저장)

어려웠던 점

queue와 stack을 어떤 구현체로 초기화할지 선택하는 데 고민이 있었다.
Java에는 Stack 클래스가 있지만 오래된 동기화 기반 클래스이며 성능이 떨어지기 때문에,
더 빠르고 가벼운 ArrayDeque를 stack/queue 용도로 사용하는 것이 적합하다.