백준 12015번, 가장 긴 증가하는 부분 수열 2 문제풀이, 파이썬

백준 12015번 : 가장 긴 증가하는 부분 수열 2 문제풀이 [파이썬] 

---

<문제>

 

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

---

 

 

<작성한 코드>

#가장 긴 증가하는 부분 수열2
from bisect import bisect_left

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

ans = [0]

for i in A:
  if ans[-1] < i:
    ans.append(i)
  else:
    ans[bisect_left(ans, i)] = i

print(len(ans)-1)

---

 

 

<코드 풀이>

 

이 문제는 이분탐색으로 풀 생각을 전혀 못했었는데

이분탐색을 사용해서 풀 수 있어서 꽤나 의외였다. 

본 문제는 파이썬의 bisect 라이브러리를 사용해서 풀었다. 

아래 포스팅 참고)

2023.03.14 - [백준 알고리즘] - [알고리즘] 이진 탐색 알고리즘(1)

[알고리즘] 이진 탐색 알고리즘(1)

 

 

 

 

from bisect import bisect_left

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

먼저 위처럼 bisect 라이브러리에서 bisect_left를 import 해주었고,

문제에서 요구하는 값들을 받기 위해서 N과 A라는 이름의 변수를 선언해주었다. 

 

 

ans = [0]

for i in A:
  if ans[-1] < i:
    ans.append(i)
  else:
    ans[bisect_left(ans, i)] = i

다음으로는 초기값으로 0 원소를 넣어서

ans라는 이름의 리스트를 선언해주었다. 

다음으로는 반복문을 돌면서 입력받은 A의 리스트 안에 원소들을 하나하나 확인하는 조건문을 만든다. 

ans 리스트의 마지막으로 넣은 원소보다 A 리스트 안에 원소의 크기가 작다면 

ans.append()를 통해 리스트에 원소를 추가해주게 된다. 

 

 

print(len(ans)-1)

마지막으로 출력을 해주는 부분에서는

우리가 ans 리스트에 초기값으로 넣어준 0을 제외해야하기때문에

ans 리스트의 길이에서 1을 빼준 값을 출력해준다.