[자바]백준 25630번 팰린드롬 소떡소떡 [문자열][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

문제 (그냥 안보고 문제 설명만 봐도 된다)

소떡소떡은 기다란 꼬치에 소시지와 떡을 끼운 음식이다. 편의상 소떡소떡을 알파벳 s와 t로만 구성된 길이 N의 문자열로 생각하자. 알파벳 s는 소세지를, t는 떡을 의미한다.

위 그림은 길이가 7인 소떡소떡의 예시이다. 유진이는 소떡소떡을 먹기 전에 소떡소떡을 팰린드롬 소떡소떡으로 만들려고 한다. 팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 예를 들어 sts, tsst, tt는 팰린드롬이다.

유진이는 특별한 마법을 사용해서 꼬치에 꽂힌 소시지 하나를 떡으로 바꾸거나, 반대로 떡 하나를 소시지로 바꿀 수 있다. 위 그림은 마법을 한 번 사용해서 떡 하나를 소세지로 바꾼 그림이다.

위 그림은 마법을 한 번 더 사용해서 떡 하나를 소세지로 바꾼 그림이다. 이제 이 소떡소떡은 팰린드롬 소떡소떡이 되었다.

유진이가 먹으려고 하는 소떡소떡이 주어질 때, 이 소떡소떡을 팰린드롬 소떡소떡으로 만들기 위해서는 마법을 최소 몇 번 사용해야 할까?

 

입력

첫째 줄에 소떡소떡의 길이 N(1≤N≤100)$N(1 \le N \le 100)$이 주어진다.

둘째 줄에 소떡소떡을 의미하는 길이 N의 문자열이 주어진다. 이 문자열은 알파벳 s와 t로만 구성되어 있다.

 

출력

소떡소떡을 팰린드롬 소떡소떡으로 만들기 위해서 마법을 최소 몇 번 사용해야 하는지 출력한다.

 

예제

알고리즘 분류

• 구현
• 문자열

문제 설명

문제의 설명이 굉장히 길지만, 그냥 주어진 단어를 앞뒤가 똑같은 단어로 만들기 위해서 최소한 소와 떡을 몇 번 바꿔줘야 하는 문제이다.

 

해설

해당 문제는 홀수와 짝수를 구분지어서 생각해 보고, 아 홀수든 짝수든 상관없이 코드를 짜도 되겠구나 알면 된다.

위의 예제 중 하나로 예시를 들어보겠다.

ststtss는 7자리 숫자로 홀수이다.

여기서 가운데 t가 어떤 문자이든 앞 3자리와 뒤 3자리 같으면 앞뒤가 똑같은 팰린드롬 단어가 된다.

즉, 홀수든 짝수든 짝수로 생각하고 문제를 풀면 된다.

문제는 단어를 직접 바꿔주는 게 아니고 몇 번을 바꾸는지 물어보는 것이기 때문에 아래처럼 풀면 된다.

가운데를 기준으로, 앞 단어는 처음부터, 뒤 단어는 마지막부터 순서대로 두 알파벳을 비교하고 다른 알파벳이면 카운트(+) 해주면 된다.

 

코드

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); //글자수
        String s = br.readLine(); // 소떡소떡 단어
        
        int cnt = 0;
        for (int i = 0; i < s.length() / 2; i++) {
            cnt += s.charAt(i) != s.charAt(s.length() - 1 - i) ? 1 : 0;
        }
        
        bw.write(cnt + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}