프로그래머스 - 가장 긴 펠린드롬
: 휴.. 시간 초과(효율성 1번) 때문에 별짓을 다해본 문제이다. 내 풀이가 잘못된건가 하여 분할정복법도 써가며 풀어봤지만 불가능한 방법이었고, 결론적으로 파이썬 내장 함수를 쓸 때 시간복잡도를 잘알고 써야겠다는 생각이 든다.
문제 해석
: 문제 자체는 간단하다. 주어진 문자열에서 '펠린드롬'을 찾되 가장 긴 펠린드롬의 길이를 찾아서 리턴하면 된다. 이 때, 펠린드롬이란 뒤집었을 때 똑같은 문자열을 말한다. 따라서 "a" 이것도 뒤집으면 똑같이 "a"이므로 디폴트는 1인 것이다.
문제 설계
: 완전탐색으로 풀면 2,500 * 2,500(최대) 6,250,000번이므로 1초 내로 해결 가능하다. 방법은 뒤에서부터 기준점을 하나씩 잡으면서 이중 for문으로 푸는데, 2depth for문에서 0부터 시작해서 기준점 바로 직전까지를 탐색한다. 즉, 0부터 기준점까지의 단어와 그것을 뒤집었을 때의 단어가 같은지 비교 => 0+1=1부터 기준점까지의 단어와 그것을 뒤집었을 때의 단어가 같은지 비교 => 1+1=2 부터.....
이렇게 하다보면 가장 긴 펠린드롬을 찾을 수 있다. 하지만, 이방법으로 풀었을 때 시간초과가 일어났는데, 그 이유는 먼저, 나는 이것을 풀 때 s(string)를 받아서 list로 변환한 다음에 각각의 펠린드롬 판단 시행에서 reversed를 하고, join을 했다. 그러나 파이썬의 함수인 join은 O(N)의 시간복잡도를 갖고, reversed도 마찬가지이다(** [::-1]의 방법으로 뒤집는 것보다 reversed를 쓰는 것이 복사한 것을 저장하지 않기 때문에 더 빠르다고 한다 => 참고 링크). 그렇기 때문에 다른 방법으로 펠린드롬을 확인해야한다. 이 때, 생가각한 것이 굳이 list로 만들지 않아도 되겠다는 것이다. 내가 왜 처음부터 list로 접근했는지 모르지만 문자열 상태로도 충분히 풀 수 있는 문제였다.
문제 풀이
def solution(s):
answer = 1
for idx in range(len(s)-1,0,-1):
if idx+1 <= answer:
break
for j in range(0,idx):
num = len(s[j:idx+1])
if answer >= num:
break
if s[j:idx+1] == s[j:idx+1][::-1]:
answer = num
break
return answer
: 이게 내 최종 풀이이다. 중간중간에 break문은 불필요한 시행을 안하기 위해서다. 나는 뒤에서부터 탐색을 하기 때문에 만약에 뒷부분에서 최대 길이가 9이 나왔으면 그 앞에 길이가 8,7,6 인 부분은 애초에 탐색할 필요가 없다. 아무리 그 부분에서 최대길이가 나와도 9보다는 아래일 것이기에.
def solution(s):
l = list(s)
answer = 1
for idx in range(len(l)-1,0,-1):
if idx+1 <= answer:
break
for j in range(0,idx):
num = len(l[j:idx+1])
if answer >= num:
break
if l[j:idx+1] == l[j:idx+1][::-1]:
answer = num
break
return answer
: 위의 코드는 string을 list로 바꿔서 풀었던 경우인데, 이 경우 효율성 1번에서 시간초과가 걸린다. 보면 알지만 차이라고는 list() 메서드를 써준 것 뿐이다..
코멘트
: 파이썬 내장 함수를 막쓰면 안되고 효율성 측면에서 고려를 해야한다. 전부다 O(1)이 아니다!(당연하게도). 또한, [::-1] 이렇게 하면 뒤집을 수 있다는 것 알아두자. 이런 펠린드롬 유형에서 유용하게 쓸 수 있을듯.
