백준

[백준 1254번][Java] 팰린드롬 만들기

2023. 4. 3. 18:59

1254번: 팰린드롬 만들기 (acmicpc.net)

 

1254번: 팰린드롬 만들기

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는

www.acmicpc.net

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

풀이

  • 입력 받은 문자열을 반대로 뒤집은 다음 비교하여 팰린드롬인지 확인 ("abab" -> "baba")
  • 팰린드롬이 아니기 때문에 reversePalindrome 실행
  • ex) i = 0, split = "b", reverseSplit = "b" -> 팰린드롬이므로 n = 1
          i = 1, split = "ba", reverseSplit = "ab" -> 팰린드롬이 아니므로 n 업데이트 X
          i = 2, split = "bab", reverseSplit = "bab" -> 팰린드롬이므로 n = 3
          i = 3, split = "baba", reverseSplit = "abab" -> 팰린드롬이 아니므로 n 업데이트 X
  • 입력 받은 문자열의 길이 * 2 - reversePalindrome() = 5

s.length() * 2 - reversePalindrome() 수식이 나온 이유

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        System.out.println(palindrome(s));
    }

    public static int palindrome(String s) {
        String reverseStr = new StringBuffer(s).reverse().toString();

        // 주어진 문자열이 팰린드롬인지 확인
        // 팰린드롬이 아니라면 reversePalindrome을 이용해 값을 얻고
        // 팰린드롬이라면 주어진 문자열의 길이를 반환
        if (!s.equals(reverseStr)) {
            return s.length() * 2 - reversePalindrome(reverseStr);
        } else {
            return s.length();
        }
    }

    public static int reversePalindrome(String s) {
        int n = 0; // 팰린드롬을 만들 수 이쓴 문자열 길이를 담을 변수

        // 한 글자씩 더해가면서 팰린드롬을 만들 수 있는 최대 길이를 구한다.
        for (int i = 0; i < s.length(); i++) {
            String split = s.substring(0, i);
            String reverseSplit = new StringBuffer(split).reverse().toString();

            if (split.equals(reverseSplit)) {
                n = split.length();
            }
        }

        return n;
    }
}
저작자표시 (새창열림)

'백준' 카테고리의 다른 글

[백준 11047번][Java][Greedy] 동전 0  (0) 2023.04.03
[백준 2003번][Java][투 포인터] 수들의 합 2  (0) 2023.04.03
[백준 2167번][Java][2차원배열][DP] 2차원 배열의 합  (0) 2023.04.03
[백준 11725번][Java][Tree][DFS] 트리의 부모 찾기  (0) 2023.03.27
[백준 5613번][Java] 계산기 프로그램  (0) 2023.03.27
'백준' 카테고리의 다른 글
  • [백준 11047번][Java][Greedy] 동전 0
  • [백준 2003번][Java][투 포인터] 수들의 합 2
  • [백준 2167번][Java][2차원배열][DP] 2차원 배열의 합
  • [백준 11725번][Java][Tree][DFS] 트리의 부모 찾기
dbssk
dbssk
K.Back-enddbssk 님의 블로그입니다.
dbssk
K.Back-end
dbssk
  • 분류 전체보기 (220)
    • 끄적 (0)
    • TIL (8)
      • Trouble Shooting (1)
    • Programmers (94)
      • Lv.0 (29)
      • Lv.1 (40)
      • Lv.2 (25)
    • 백준 (15)
    • 구름 (0)
    • Computer Science (79)
      • 컴퓨터 구조 (3)
      • Operating System (18)
      • 알고리즘 (9)
      • 자료구조 (11)
      • Database (10)
      • Network (8)
      • Web (12)
      • Design Pattern (8)
    • Spring (2)
    • Languages (13)
      • Java (13)
    • 북 스터디 (9)
      • 스프링 부트 핵심 가이드 (9)
      • 자바 코딩 인터뷰 완벽 가이드 (0)
    • 프론트엔드 (0)

인기 글

최근 글

태그

  • 코딩테스트
  • 백준
  • 개발자포트폴리오
  • stack
  • hash
  • 프로그래머스
  • 개발자취준
  • LV.2
  • 백엔드공부
  • java
  • 개발자취업
  • spring
  • 배열
  • Lv.0
  • 백엔드스쿨
  • LV.1
  • 해시
  • 개발자이력서
  • 스택
  • 자료구조
hELLO · Designed By 정상우.
dbssk
[백준 1254번][Java] 팰린드롬 만들기
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.