[자바] 백준 17502 - 클레어와 팰린드롬 (java)

문제 : boj17502

---

 

필요 알고리즘 개념

• 구현, 문자열
  
  • 문자열의 각 character를 파악하고, 문제의 규칙을 이해해서 구현해줘야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  팰린드롬은 앞에서 읽으나 뒤에서 읽으나 동일해야 한다. 그 말인즉, 문자열의 양 끝에서 포인터를 두고 중간으로 점점 오면서 두 포인터가 가르키는 문자가 전부 동일해야 함을 의미한다. 아래의 경우 '3'과 '4'가 다르므로 팰린드롬이 아님을 알 수 있다.

 

  팰린드롬이 어떤것인지 이해했다면 간소화해서 구현만 잘 해주면 된다. 문자열의 길이가 n 이므로, n/2 (정수가 아닐 경우 내림)까지 확인하면 팰린드롬임을 확인할 수 있는데, 이 문제는 '?'에 적절한 문자를 넣어줘야 하므로 n/2+1 까지 확인해야 한다(홀수일 경우 중앙 문자까지 확인해야 하므로). 위에서 두 포인터로 점점 중앙으로 오는걸 생각해보면 경우의 수는 다음과 같다.

 

1. 앞쪽의 문자가 '?', 뒤쪽은 '?'가 아님 -> 뒤의 문자를 앞쪽에 넣어준다.

2. 뒤쪽의 문자가 '?', 앞쪽은 '?'가 아님 -> 앞의 문자를 뒤에 넣어준다.

3. 둘 다 '?' -> 아무 문자나 넣어주면 된다. 내 경우엔 'a'를 넣어줬다.

 

int n = Integer.parseInt(br.readLine());
char[] arr = br.readLine().toCharArray();
for (int i = 0; i < n/2+1; i++) {	// i를 중앙 문자까지 확인한다.
    char cur = 'a';	// 둘 다 '?'일 경우 들어갈 문자이다. 내 경우엔 'a'로 정했다.
    if (arr[i] != '?') cur = arr[i];	// 앞쪽이 '?'가 아니면
    if (arr[n-i-1] != '?') cur = arr[n-i-1];	// 뒤쪽이 '?'가 아니면
    arr[i] = arr[n-i-1] = cur;	// 3가지 경우의 수 중 어떤것에 걸렸는진 중요하지 않다. 아무튼 앞쪽, 뒤쪽 전부 cur로 변경하면 된다 ㅋㅋ
}
System.out.println(String.valueOf(arr));

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[] arr = br.readLine().toCharArray();
        for (int i = 0; i < n/2+1; i++) {
            char cur = 'a';
            if (arr[i] != '?') cur = arr[i];
            if (arr[n-i-1] != '?') cur = arr[n-i-1];
            arr[i] = arr[n-i-1] = cur;
        }
        System.out.println(String.valueOf(arr));
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}