문제 이해 단계
https://school.programmers.co.kr/learn/courses/30/lessons/12904?
팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 뜻한다.
입력으로 문자열 s가 주어질 때,
s의 부분 문자열 중에 가장 긴 팰린드롬의 길이를 구하는 문제
문제 접근 단계
제한사항부터 살펴보자.
문자열의 길이 s는 2,500 이하의 자연수이고, 알파벳 소문자로만 구성되어 있다.
팰린드롬이라는 좌우대칭 규칙성을 판단할 때는 보통 스택을 사용한다.
이 문제에서 사용하려고 했는데,
각 자리마다 스택을 사용하여 넣었다 뺐다 하는 것은 굉장히 비효율적이다.
그리고 예전에 백준 포스팅에서 이런 유사한 문제를 다룬 적이 있다.
https://howudong.tistory.com/319
[C++] 백준 10942 - 팰린드롬?
문제 이해 단계 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경
howudong.tistory.com
여기서는 팰린드롬의 길이를 구하는 것은 아니지만,
일정 구간이 팰린드롬인지를 판단하는 문제이다.
사실 이 문제의 개념도 해당 문제와 동일하다.
이 핵심 개념을 그대로 따라간다.
d [i][j] = k → i번째 인덱스부터 j번째 인덱스까지의 팰린드롬의 최대 개수는 k이다.
라고 하자.
인덱스가 0이 아닌 1부터 시작한다고 가정하고 d [1][7]을 살펴보자.
첫 번째 인덱스부터 마지막 인덱스까지,
즉 전체 문자열이 팰린드롬이 되려면 어떻게 돼야 할까?
1. 첫 번째 원소와 마지막 원소가 서로 같아야 한다.
2. 첫 번째 원소와 마지막 원소를 뺀 문자열로 이뤄져 있는 것이 팰린드롬이어야 한다.
이 두 가지를 만족해야 한다.
여기서 첫 번째 원소와 마지막 원소를 뺀 문자열이라는 것은? d [2][6]이다.
한마디로 d [2][6]이 팰린드롬이어야 된다는 것이다.
그럼 d [2][6]이 팰린드롬이 판단하는 법은?
d [1][7]이랑 똑같은 방법으로 판단한다.
똑같은 방식으로 하다 보면 가장 오른쪽 그림처럼 된다.
(1번 조건에서 아무도 걸리지 않을 때를 가정)
원소가 하나일 때는 팰린드롬이고, 길이는 1이다.
그러면 d [3][5]는 팰린드롬이 맞다는 것을 확신할 수 있다.
길이는 어떻게 되는가? 당연히 d [4][4] + 2를 하면 된다.
팰린드롬은 두 개씩 비교하여 짝을 맞춘 것이기 때문이다.
최종적으로 점화식은 이렇게 나오게 된다.
if(arr [i] == arr [j] && dp [i][j-1]!= -1)
dp [i][j] = dp [i+1][j-1] + 2
else dp [i][j] = -1
여기서 -1은 팰린드롬이 아님을 뜻한다.
이를 bottom-up 방식이든 top-down 방식이든 본인이 편한 대로 구현하면 된다.
이제 문제 구현단계에서 C#과 C++ 코드로 모두 구현해 보자.
문제 구현 단계
C++로 구현한 코드
↓
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[2501][2501] = {0,};
int arr[2501] = {0,};
int solution(string s)
{
int answer=0;
for(int i = 0; i < s.length(); i++) arr[i+1] = s[i];
for(int i = s.length(); i > 0; i--){
for(int j = i; j <= s.length(); j++){
// 원소가 1개일때는 무조건 팰린드롬, 길이가 1
if(i == j) dp[i][j] = 1;
// 점화식대로 해줌
else if(arr[i] == arr[j] && dp[i+1][j-1] != -1){
dp[i][j] = dp[i+1][j-1] + 2;
}
else dp[i][j] = -1;
// 길이가 가장 긴 것을 정답으로
answer = max(answer,dp[i][j]);
}
}
return answer;
}↑
C#으로 구현한 코드
↓
using System;
public class Solution {
static int[,] dp = new int[2501,2501];
static char[] arr = new char[2501];
public int solution(string s) {
for(int i = 0; i < s.Length; i++) arr[i+1] = s[i];
int answer = 0;
for(int i = s.Length; i > 0; i--){
for(int j = i; j <= s.Length; j++){
// 원소가 1개 일때는 무조건 팰린드롬, 길이가 1
if(i == j) dp[i,j] = 1;
// 점화식대로 해줌
else if(arr[i] == arr[j] && dp[i+1,j-1] != -1){
dp[i,j] = dp[i+1,j-1]+2;
}
else dp[i,j] = -1;
// 길이가 가장 긴 것을 정답으로
answer = Math.Max(answer,dp[i,j]);
}
}
return answer;
}
}↑
두 코드 다 별로 다를 것이 없다.
dp 문제이기 때문에 풀이는 매우 간단하다.
여기서 팰린드롬이 아님을 뜻함을 -1로 표현한 이유는
i와 j가 1이 차이 날 때를 대비한 것이다.
만약 0을 팰린드롬이 아님을 의미하게 한다면 i와 j가 연속될 때 예외가 발생한다.
dp [1][2]를 점화식을 적용하면 d [2][1]이 되기 때문에 0이 나오는데
이때 팰린드롬이어도 팰린드롬이 아니게 될 수 있기 때문이다.
풀이는 여기까지이다.
시행착오
백준에서 예전에 풀어본 문제와 굉장히 유사했기 때문에 푸는데 문제는 없었다.
게임 서버 프로그래밍에 익숙해지기 위해
프로그래머스로 넘어오고 알고리즘을 C#으로 풀기 시작했는데, 아직 어색하기는 하다.
파이팅
생활비..