[Java] 백준 1259번: 팰린드롬수 with Deque

문제 url:
팰린드롬수

문제:

🤔 문제 알아보기

---

팰린드롬수란, 앞으로 하나 뒤로 하나 똑같은 단어 혹은 수를 팰린드롬이라고 한다.
앞뒤가 똑같은 전화번호

그러면, 간단하다 단어를 배열로 만들어서 이를 맨앞과 맨뒤를 비교하며, 인덱스를 늘려주면 충분히 풀 수 있는 문제이다.

필자는 이를 Deque를 활용해서 풀어보고자 한다.
Deque는 양방향 큐로, 앞의 자리 혹은 뒤의 자리에 값을 삽입 혹은 삭제할 수 있는 자료구조이다.

Deque가 무엇인지 궁금한 분은 밑에 링크를 보고오시면 이해가 될 것이다.
[Java] Deque(데크 / 덱) 정리 및 사용법

즉, 1,2,3,2,1 배열에 이런 값이 존재한다면! 첫 번쨰와 마지막값을 삭제하며 반환받는 poll()과 pollLast()메서드를 이용하여 풀 수 있다.

🐱‍👤 실제 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true) {
            Deque<Character> deque = new LinkedList<>();
            String str = br.readLine();

            if(str.equals("0")) {
                break;
            }

            for(int i = 0; i <str.length(); i++) {
                deque.offer(str.charAt(i));
            }

            boolean is_pal = true;
            for(int i = 0; i < str.length() / 2; i++) {
                if(!deque.poll().equals(deque.pollLast())) {
                    System.out.println("no");
                    is_pal = false;
                    break;
                }
            }
            if(is_pal) {
                System.out.println("yes");
            }
        }
    }

}

앞과 뒤에서 접근하기 때문에 반복은 크기의 절반만큼만 진행하면 될 것이다.

🤢 트러블 슈팅 및 풀이 해석

---

			for(int i = 0; i < str.length() / 2; i++) {
                if(!deque.poll().equals(deque.pollLast())) {
                    System.out.println("no");
                    is_pal = false;
                    break;
                }
            }

이 부분에서 필자가 잠시 막혀서 풀이를 하자면,
반복 횟수에서 왜 deque.size()가 아닌 str.length() 즉, 단어의 길이를 이용했냐면 필자는 poll과 pollLast를 이용해 값을 제거하며 생긴 반환 값을 확인하는 과정을 거쳤다.
그래서 값이 삭제되면 자연스레 deque.size()가 삭제된 만큼 삭제되기 때문에 문제가 발생하게 된다.

또한 앞뒤가 다른 문자일 경우 break; 를 통해 반복문을 빠져나가는 데, 만약 이를 하지 않을 경우 1212라는 반례를 넣게 되면 no가 두번 출력하게 된다.
이처럼 우리는 no라는 값을 한번만 받기 위해서 앞뒤가 한번만 달라도 팰린드롬수가 아니기 때문에 break를 통해 조건에 맞는 출력을 얻을 수 있다.