백준 / 가장 긴 증가하는 부분 수열 5 / 14003번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 가장 긴 증가하는 부분 수열 5 / 14003번 (플래티넘 5단계)

문제 사이트: https://www.acmicpc.net/problem/14003

 

문제 설명

---

나의 풀이

def solution(a, arr):
    answer = [-1000000001]

    for idx in range(a):
        # 마지막 원소
        last_value = answer.pop()
        # 다시 추가
        answer.append(last_value)

        # 마지막 원소보다 클 경우 추가
        if arr[idx] > last_value:
            answer.append(arr[idx])
        else:
            left = 0
            right = len(answer)

            while left < right:
                # 중간 부분
                center = (left + right) // 2
                # 중간 보다 클 경우
                if answer[center] < arr[idx]:
                    left = center + 1
                else:
                    right = center
            answer[right] = arr[idx]

    print(len(answer) - 1)
    for i in range(1, len(answer)):
        print(answer[i], end = ' ')

def main():
    a = int(input())
    arr_i = list(map(int, input().split()))
    solution(a, arr_i)

main()

이전에 풀었던 문제랑 비슷해서 똑같이 이분 탐색을 이용해서 문제를 해결하려고 했지만 틀렸다. 이 코드는 LIS의 길이는 정확히 계산할 수 있지만, 실제 LIS를 복원하는 부분이 누락되어있다는 사실을 알게되었다.

수정사항

• lis 리스트는 길이를 추정하는 데 사용합니다.
• indices와 prev 배열을 추가하여 각 원소가 LIS의 어느 위치에서 왔는지 추적합니다.
• 최종적으로 LIS를 복원하는 과정을 추가했습니다.

추가된 점

1. 경로 추적 (indices와 prev):
   • indices: LIS의 각 단계에서 마지막 원소의 인덱스를 저장합니다.
   • prev: 각 원소가 LIS에서 이전에 연결된 원소의 인덱스를 저장합니다.
2. 복원 과정:
   • indices의 마지막 원소부터 prev를 따라가며 LIS를 역으로 복원합니다.

예: A = [10, 20, 10, 30, 20, 50]

1. 처리 중:
   • lis = [10], indices = [0]
   • 20 추가: lis = [10, 20], indices = [0, 1], prev = [-1, 0]
   • 10 덮어쓰기: lis = [10, 20], indices = [2, 1], prev = [-1, 0, -1]
   • 30 추가: lis = [10, 20, 30], indices = [2, 1, 3], prev = [-1, 0, -1, 1]
   • 20 덮어쓰기: lis = [10, 20, 30], indices = [2, 4, 3], prev = [-1, 0, -1, 1, 1]
   • 50 추가: lis = [10, 20, 30, 50], indices = [2, 4, 3, 5], prev = [-1, 0, -1, 1, 1, 3]
2. 복원:
   • indices에서 마지막 인덱스 5부터 시작: 50 → 30 → 20 → 10.
   • LIS: [10, 20, 30, 50].

반례: A = [50, 40, 30, 20, 10, 5]

• lis = [5] (LIS는 길이 1이지만, 복원 과정에서 정확히 [5]를 반환).

수정된 코드

def solution(a, arr):
    import bisect
    
    # LIS를 추적하기 위한 리스트
    lis = []
    # LIS를 복원하기 위한 경로 저장
    indices = [-1] * a
    prev = [-1] * a
    
    for i in range(a):
        # 이분 탐색을 통해 LIS의 위치를 찾음
        pos = bisect.bisect_left(lis, arr[i])
        
        if pos == len(lis):
            lis.append(arr[i])
        else:
            lis[pos] = arr[i]
        
        # 인덱스 추적
        indices[pos] = i
        if pos > 0:
            prev[i] = indices[pos - 1]
    
    # LIS 길이와 복원
    lis_length = len(lis)
    lis_seq = []
    cur = indices[lis_length - 1]
    while cur != -1:
        lis_seq.append(arr[cur])
        cur = prev[cur]
    
    lis_seq.reverse()
    print(lis_length)
    print(*lis_seq)

def main():
    a = int(input())
    arr_i = list(map(int, input().split()))
    solution(a, arr_i)

main()

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/188

[알고리즘] 이분 탐색(Binary Search)