[백준_12015] 가장 긴 증가하는 부분 수열 2

문제 보기: https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

새로 사용한 함수

bisect.bisect_left( 탐색 문자열, 탐색 값)

이진 탐색을 수행해주는 함수로 파이썬에서 지원한다. 

결과 값으로는 해당 구간에서 값이 들어가야 하는 위치를 알려준다 left와 right가 있으며 left는 왼쪽으로 right는 오른쪽으로 알려준다.

 

 

풀이 과정

코드 2번 방식으로 이전에 풀었던 것을 생각하면서 풀었고 결괏값이 계속 맞게 나오는데 실패라고 결과가 계속 나와서 다른 답을 찾아보았으나 왜 틀렸는지 이해가 되지 않는다.

1. 기본적인 풀이과정은 이진 탐색을 수행해서 결과 수열을 만들 때 시간 복잡도를 고려하여 작성하면 된다.

2. 처음에 수열을 찾을 값을 배열로 입력받고 해당 값을 순회하면서 점점 커지도록 만들어준다.

3. 기본적인 내용으로는 다음으로 탐색하는 값이 이전 값보다 큰지 작은 지를 비교하면서 진행하게 되지만 만들어진 수열에서 이진 탐색을 하여 추가적인 경우의 수가 있을 가능성을 확인한다.

4. 1~3번 내용을 반복적으로 수행하고 마지막으로 만들어진 배열의 값의 길이를 출력한다.

 

코드 1번의 풀이 방식도 2번과 같아서 같은 풀이과정으로 남겨두지만 1번은 성공 2번은 실패한 코드

 

코드

코드 1

import sys
import bisect
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

result = []
result.append(arr[0])

for i in range(1, N):
    if arr[i] > result[-1]:
        result.append(arr[i])
    else:
        index = bisect.bisect_left(result, arr[i])
        result[index] = arr[i]

print(len(result))

 

코드 2

import bisect

i = int(input())

num = [] * i
max = []
str = input().split()

for _ in str:
    num.append(_)

max.append(num[0])

# print(":::::::: process check ::::::::")
for i, check in enumerate(num[1: len(num)], start=1):
    if num[i - 1] < num[i]:
        max.append(num[i])
    else:
        index = bisect.bisect_left(max, num[i])
        # print(f"{i} : {index}")
        max[index] = num[i]
    # print(i, check)

# print(":::::::: process check ::::::::")

# max.append(num[-1])
# print(max)
print(len(max))