[백준 #10066] 팰린드롬 (시간초과, 메모리초과.. 그저 기록용 코드)

오늘은 예제는 맞췄는데 시간, 메모리 초과가 뜬 문제를 가져왔습니다. 

정답이 뭔지 몰라서 더욱 답답한.. 하지만 DP를 이용한 방식, Two Pointer를 이용한 방식 모두 예제는 맞춰서.. 

나중에 좀 더 코딩을 잘하는(?) 제가 참고하도록 기록해놓겠습니다.

 

문제

https://www.acmicpc.net/problem/10066

10066번: 팰린드롬

 

코드 및 풀이

 

우선 'bacab'과 같이 팰린드롬인 문자열의 조건은, 

1) 시작점의 문자열과 끝점의 문자열이 같고, ('bacab'의 경우 양끝이 'b'로 같습니다)

2) 시작점, 끝점을 제외한 문자열 역시 팰린드롬입니다. ('bacab'의 경우 양끝을 제외한 'aca'역시 팰린드롬입니다) 

 

아래는 문제에 대한 풀이입니다.

 

1. Two Pointer를 이용한 방식

s='abacaba'
result={}
answer=[]
for i in range(len(s)):
  for j in range(0,2):
    left,right=i,i+j
    while left>=0 and right<len(s) and s[left]==s[right]: 
        left-=1 
        right+=1
        if s[left+1:right] not in result.keys():
            result[s[left+1:right]]=1
        else:
            result[s[left+1:right]]+=1
for i in result:
    answer.append(len(i)*result[i])
print(max(answer))

1) 팰린드롬을 Two Pointer로 구하는 원리는 아래를 참고하시면 될 것 같습니다.

https://byumm315.tistory.com/entry/%EB%A6%AC%ED%8A%B8%EC%BD%94%EB%93%9C-5-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%EB%B6%80%EB%B6%84-%EB%AC%B8%EC%9E%90%EC%97%B4

[리트코드 #5] 가장 긴 팰린드롬 부분 문자열

 

2) 팰린드롬을 구하며 result 딕셔너리에 키(key)를 저장했습니다. 이때, 딕셔너리에 값(value)이 존재하면 1을 더했고 존재하지 않으면 키(key)를 만들고 값을 1로 지정했습니다. result 는 아래와 같습니다.

 

{'a': 4, 'aba': 2, 'abacaba': 1, 'aca': 1, 'b': 2, 'bacab': 1, 'c': 1}

 

3) for문을 이용해 result에서 키(key)의 길이와 해당하는 값(value)을 곱해 answer 리스트에 저장했습니다.

이후 가장 큰 값을 출력했습니다. answer 리스트는 아래와 같습니다.

 

[4, 2, 6, 1, 3, 5, 7]

 

4) 정답은 7입니다.

 

2. DP(다이나믹 프로그래밍)를 이용한 방식

s='abacaba'
n=len(s)
dp = [[0] * n for _ in range(n)]
answer=[]
answer_1=[]

for num_len in range(n):
    for start in range(n - num_len):
        end = start + num_len
        # 시작점과 끝점이 같다면 글자수가 1개이므로 무조건 팰린드롬
        if start == end:
            dp[start][end] =1
            answer.append(s[start:end+1])
        # 시작점의 글자와 끝점의 글자가 같다면
        elif s[start] == s[end]:
        	# 두 글자짜리 문자열이라면 무조건 팰린드롬
            if start + 1 == end: 
                dp[start][end] = 1
                answer.append(s[start:end+1])
            # 가운데 문자열이 팰린드롬이라면 팰린드롬
            elif dp[start+1][end-1] == 1: 
                dp[start][end] = 1
                answer.append(s[start:end+1])
                
from collections import Counter
for i in Counter(answer):
    answer_1.append(len(i)*Counter(answer)[i])
print(max(answer_1))

1) 문자열 길이의 행과 열을 가진 DP Table dp를 만듭니다. 

2) 이중for문을 통해 시작점과 끝점사이 길이가 0일때부터 n일때까지 범위를 지정합니다. 

따라서 길이가 0인 부분문자열부터 n인 부분문자열까지 확장하는 방식으로 팰린드롬을 찾습니다.

 

이것은 크기가 작은 부분문자열부터 팰린드롬 유무를 확인하고 문자열의 크기를 조금씩 크게 만들면서 팰린드롬 유무를 확인한다는 점에서 DP의 Bottom - Up 방식과 유사합니다.

 

DP에서 문제가 팰린드롬 유무를 찾기라면 작은 문제를 풀면서 큰 문제의 해답을 찾는다는 점에서 유사합니다.

 

2-1) 예를 들면, 길이가 7인 'abacaba'가 팰린드롬인지 알려면, 양 끝점을 봅니다.

양 끝점이 'a'로 같기 때문에, 팰린드롬일 가능성이 있습니다.

 

이제, 양 끝점을 제외한 나머지 문자열'bacab'가 팰린드롬인지 알아야 됩니다.

그런데, 우리는 이미 앞에서 길이가 5인 부분 문자열에 있는 팰린드롬들을 구했습니다.

 

따라서 'bacab'가 팰린드롬임을 알 수 있습니다. 

가운데에 있는 'bacab'가 팰린드롬이기 때문에, 'abacaba' 역시 팰린드롬입니다.

 

3) 문자열 안에 있는 부분문자열이 팰린드롬인 경우, dp[시작점][끝점]에 1을 부여합니다.

아래의 그림의 0번째 줄을 예로 들면, 0번째 원소와 2번째 원소가 1입니다. 즉, 시작위치가 0, 끝위치가 2인 원소 'aba'가 팰린드롬임을 의미합니다.

4) 문자열 안에 있는 부분문자열이 팰린드롬인 경우, 해당 문자열을 answer 리스트에 저장합니다.

answer 리스트는 다음과 같습니다.

 

['a', 'b', 'a', 'c', 'a', 'b', 'a', 'aba', 'aca', 'aba', 'bacab', 'abacaba']

 

5) answer 리스트 안에 있는 중복 문자열과 빈도수를 구하기 위해 collections에서 Counter를 임포트합니다.

문자열의 길이와 빈도수를 곱한 후, 가장 큰 값을 출력합니다. Counter 함수를 적용한 결과는 다음과 같습니다.

 

Counter({'a': 4, 'aba': 2, 'abacaba': 1, 'aca': 1, 'b': 2, 'bacab': 1, 'c': 1})

 

6) 정답은 7입니다.

 

참고

https://velog.io/@himi/%EB%B0%B1%EC%A4%80-10942.-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC

[파이썬] 백준 10942. 팰린드롬?