[Baekjoon]백준 11054 가장 긴 바이토닉 부분 수열(골드 4) - Python

문제설명

문제를 살펴보면 이전에 풀었던 11053 가장 긴 증가하는 부분 수열의 응용 문제로 볼 수 있다

이번에는 증가하는 부분이외에도 감소하는 부분 수열도 찾아야한다

이전 코드를 활용하여 작성하면 될거같다는 생각이 들었고, 각 자리마다 가장 긴 증가, 감소 부분 수열의 길이를 저장한

리스트를 만들어주고 그 리스트의 index의 값의 합 중에서 가장 큰 값을 출력하는 로직으로 작성하였다

 

예시를 통해 쉽게 설명하자면 가장 긴 증가하는 부분 수열의 길이가 저장된 리스트가 1 2 3 2 1 4 라고 가정하고,

가장 긴 감소하는 부분 수열의 길이가 저장된 리스트가 1 2 3 4 2 1 라고 가정하자

(임의로 설정한 수이기 때문에 실제와는 다를수 있음)

다음과 같은 상황일때 index가 0인 경우 최대 길이는 1이 될것이다

왜냐하면 감소와 증가의 합 -1인 경우로 계산해야하기 때문이다 -1을 하지않으면 중복되는 부분이 발생한다

이러한 방식으로 index를 따라가며 검색하다보면 5가 가장 긴 경우의 수임을 확인할 수 있다

(index가 2, 3인 경우)

from bisect import bisect_left

length = int(input())
seq = (list(map(int, input().split())))

result_min = [0] * length # 최대 길이
min_seq = [] # 작은 값 저장

# 증가하는 부분
for i in range(length):
    pos = bisect_left(min_seq, seq[i])
    if pos == len(min_seq):
        min_seq.append(seq[i])
    else:
        min_seq[pos] = seq[i]
    result_min[i] = pos + 1
        
result_max = [0] * length
max_seq = [] # 큰 값 저장

# 감소하는 부분
for i in range(length - 1, -1, -1):  # 뒤에서부터 탐색
    pos = bisect_left(max_seq, seq[i])
    if pos == len(max_seq):
        max_seq.append(seq[i])
    else:
        max_seq[pos] = seq[i]
    result_max[i] = pos + 1
        
Answer = 0
for i in range(length):
    Answer = max(Answer, result_min[i] + result_max[i] - 1)

print(Answer)

이전 코드와 달라진 점은 증가, 감소를 계산하는 반복문의 내용이 조금 달라졌다

이번에는 먼저 이진탐색을 통해 값을 넣을 수 있는 곳을 탐색한다 그 이후에 그 index의 값이 min_seq의 길이와 같으면

해당 값을 append()해주고(→ 더 긴 증가 수열이 가능하다는 뜻), 아니라면 값을 바꿔넣어준다 

그리고 마지막 과정에서 현재 증가 수열의 길이를 저장해준다

감소하는 부분은 동일한 과정이긴 하나, 이 과정을 뒤에서부터 실행하면 감소하는 부분 수열의 길이를 구할 수 있다

마지막에 해당 수열들을 확인하여 최댓값을 찾아내면 끝이다