[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

https://www.acmicpc.net/problem/12015

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 주어진 수열을 순서대로 봤을 때 가장 긴 증가하는 부분 수열을 찾아 그 길이를 구하는 문제이다.

수열의 값을 하나씩 불러오며 바로 이전 값보다 크면 바로 추가하고 이전 값보다 크지 않으면 해당 값이 들어갈 자리를 찾아 새로 저장한다.

값이 들어갈 자리를 찾는 방법은 결과 수열을 저장한 리스트의 양쪽 끝을 기준으로 잡고 중간 지점을 찾아 해당 위치의 값과 비교한다.

만약 넣을 값이 중간 위치의 값보다 크면 더 뒤쪽에 값을 넣어야 하므로 앞쪽 기준을 중간 지점 다음으로 옮긴다.

반면에 넣을 값이 중간 위치의 값보다 크지 않으면 더 앞쪽에 값을 넣어야 하므로 뒤쪽 기준을 중간 지점으로 옮긴다.

계속 반복하다가 앞쪽 기준이 뒤쪽 기준보다 뒤로 가면 반복을 종료하고 뒤쪽 기준의 위치에 가져온 값을 새롭게 저장한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 수열의 크기를 입력받는다. N = int(sys.stdin.readline())
3. 수열을 이루고 있는 값들을 입력받아 리스트로 저장한다. A = list(map(int, sys.stdin.readline().split()))
4. 결과 수열을 저장할 리스트를 생성하고 0을 넣어준다. result = [0]
5. 입력받은 수열의 값을 하나씩 가져오며 for a in A
   1. 만약 가져온 값이 결과 수열에 저장된 마지막 값보다 크면 가져온 값을 결과 수열에 추가한다. if (result[-1] < a): result.append(a)
   2. 반면에 가져온 값이 결과 수열에 저장된 마지막 값보다 크지 않으면 else
      1. 가져온 값을 넣을 시작 위치를 저장할 변수를 생성하고 초기화한다. start = 0
      2. 가져온 값을 넣을 마지막 위치를 저장할 변수를 생성하고 결과 수열 크기를 저장한다. end = len(result)
      3. 시작 위치가 마지막 위치를 넘지 않으면 반복한다. while (start < end)
         1. 시작 위치와 마지막 위치를 가지고 중간 위치를 구한다. mid = (start + end) // 2
         2. 가져온 값이 결과 수열에서 중간 위치의 값보다 크면 중간 위치가 더 뒤로 가야 증가하는 수열이 되므로 시작 위치를 중간 위치 다음으로 옮긴다. if (result[mid] < a): start = mid + 1
         3. 반면에 가져온 값이 결과 수열에서 중간 위치의 값보다 크지 않으면 중간 위치가 더 앞으로 와야 증가하는 수열이 되므로 마지막 위치를 중간 위치로 옮긴다. else: end = mid
      4. 최종적으로 반복이 종료되면 결과 수열의 마지막 위치에 가져온 값을 새로 저장한다. result[end] = a
6. 가장 긴 증가하는 수열을 찾았으면 그 길이를 출력한다. (처음에 넣은 0은 제외) print(len(result) - 1)

3. 소스코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

result = [0]
for a in A:
    if (result[-1] < a):
        result.append(a)
    else:
        start = 0
        end = len(result)

        while (start < end):
            mid = (start + end) // 2
            if (result[mid] < a):
                start = mid + 1
            else:
                end = mid

        result[end] = a
    
print(len(result) - 1)