[Python][백준 16161][이분 탐색] 가장 긴 증가하는 팰린드롬 부분 수열 - 컴도리돌이

 

반응형

16161번: 가장 긴 증가하는 팰린드롬 부분수열

---

풀이과정

해당 문제를 푸는데 거의 1시간 반을 써서 해결했다. 🤣🤣
그것도 아이디어가 생각나지 않아서 다른 분의 코드를 확인하면서 해결했다.
이 문제의 핵심은 "투 포인터"로 문제를 해결해야 한다.

1.  기준점 인덱스로부터 증가하는 팰린드롬의 길이를 구해야 한다.

2. 팰린드롬의 길이는 최소 1이 될 수도 있다.
3. start, end라는 배열의 인덱스를 각각 0으로 초기화한다.
4. 기준점의 길이가 최대 2일 경우도 존재한다. (ex. 1 2 2 1 <- 중심의 길이가 2가 된다.) 그렇기 때문에 현재 위치의 중심의 길이(1)에서 중심의 길이가 2까지 될 수 있는지 확인한다.
5. 중심의 길이를 구했으면 이제는 팰린드롬인지 확인해야 한다. 추가적으로 증가하는 팰린드롬 조건도 고려해야 한다.
6. i, j의 값은 중심의 인덱스에서 시작하지 않고 중심에서 왼쪽, 오른쪽부터 시작한다. (ex. i= start-1, j= end+1)
7. 기준점으로부터 멀어질수록 현재 인덱스보다 다음 인덱스의 값이 더 작아야 한다. 그렇기 때문에 기준점의 인덱스의 값을 value에 저장하였다. (ex. value =  arr[start]) 또한 팰린드롬의 성질로 왼쪽 인덱스의 값과 오른쪽 인덱스의 값도 같아야 한다. (ex. arr[i] == arr[j])
8. 마지막으로 전체적인 가장 긴 팰린드롬의 길이를 출력해야 한다. 그렇기에 출력 값(ans)을 -1로 초기화하고, 팰린드롬의 길이를 end-start + 1로 초기화해주면서 왼쪽, 오른쪽 인덱스가 7번 조건이 성립할 때마다 길이를 2씩 증가시켜준다.
9. ans와 8번에서 계산한 팰린드롬의 길이(size) 중에 큰 값을 ans에 저장한다.
10. 마지막으로 중심(start)을 j에 저장한다.

---

풀이 코드

import sys; input = sys.stdin.readline
n,*arr = map(int,open(0).read().split()); start,end,ans = 0,0,-1
while start < n :
  end = start # 처음에 중심을 같게 설정 
  while end+1 < n and arr[end+1] == arr[start] and end - start  < 1 : end += 1 # 중심의 길이 찾기. 최대 길이 2
  # i = 왼쪽 중심(중심 길이가 2일 경우 아니면 그냥 중심이라 생각)의 왼쪽, j= 오른쪽 중심의 오른쪽, value = 중심 값, size= 현재 중심 크기(최대 2)
  i,j,value,size = start-1,end+1,arr[start],end - start + 1  
  # 왼쪽 인덱스 i >=0 , 오른쪽 인덱스 j < n , 팰리드롬 성질 -> 왼쪽인덱스 값 = 오른쪽 인덱스 값, 증가하는 팰린드롬 조건 -> 증가하는 인덱스 값 < 이전 인덱스 값 
  # (성립할경우 ) 왼쪽 인덱스 증가 (i-1), 오른쪽 인덱스 증가(j+1),팰린드롬 길이 증가(size+2), 이전 인덱스 값 저장(value = arr[i] or value = arr[j])
  while i >= 0 and j < n and arr[i] == arr[j] and arr[i] < value : value,i,j,size = arr[i],i-1,j+1,size+2 
  # 출력값(ans)와 팰린드롬의 길이(size) 비교해서 큰 값 ans에 저장, 중심 값 이동 (start = j)
  ans,start = max(ans,size),j
print(ans)