Algorithm
[Python] 백준 1592 - 회문은 회문아니야!! (문자열)
limsw
2022. 10. 13. 13:59
반응형
제약 사항
- 시간 제한 : 2 초
- 메모리 제한 : 512MB
문제
입력
출력
예제 입력
ABCBA // 예제입력 1
PALINDROME // 예제입력 2
ZZZ // 예제입력 3예제 출력
4 // 예제 출력 1
10 // 예제 출력 2
-1 // 예제 출력 3잘못된 접근 방식
s = input()
answer = -1
for i in range(len(s)-1):
temp = s[i]
for j in range(i+1, len(s)):
temp += s[j] # 부분 문자열
reverse = temp[::-1] # 부분 문자열을 뒤집은 변수
if len(temp) >= 2 and temp != reverse:
answer = max(answer, len(temp))
print(answer)브루트포스 알고리즘을 이용하여 부분 문자열이 팰린드롬인지 확인한 뒤, 팰린드롬이 아니라면 해당 문자열의 길이를 저장하는 방법으로 코드를 작성했다. 그러나 2중 반복문으로 구현하면 문자열의 최대 길이가 50만 이므로 시간 초과가 발생했다.
그러나 다시 문제를 생각해보면, 팰린드롬이 아닌 가장 길이가 긴 부분 문자열을 구하는 것이므로 만약 주어진 문자열이 팰린드롬이라면 (주어진 문자열의 길이-1)은 당연히 팰린드롬이 되지 않을 것이고 해당 길이가 정답이 된다는 것을 깨달았다.
또한, 주어진 문자열이 팰린드롬이 아니라면 해당 문자열의 길이가 정답이라는 것을 알 수 있었다.
위 내용을 통해 해당 문제의 답을 구하기 위한 조건은 다음과 같다.
- 문자열의 길이가 1 또는 문자열의 알파벳이 모두 반복되는 경우는 -1을 출력한다.
- 문자열이 팰린드롬이라면(ABCBA) 마지막 문자를 제외(ABCB)한 문자의 길이가 정답이 된다.
- 문자열이 팰린드롬이 아니라면 해당 문자열의 길이가 정답이 된다.
올바른 접근 방식
s = input()
len_s = len(s) # 문자열의 길이
temp = s.count(s[0]) # ZZZ 라면 맨 앞 문자인 Z의 개수를 구함
# 문자열의 길이가 1이거나 문자열이 한 가지의 문자로 이루어진 경우
if len_s == 1 or temp == len_s:
print(-1)
else:
# 문자열이 팰린드롬인 경우
if s == s[::-1]:
print(len_s-1)
# 문자열이 팰린드롬이 아닌 경우
else:
print(len_s)