[파이썬 알고리즘 문제풀이 입문] 이분탐색(결정알고리즘) & 그리디 알고리즘 - 증가수열 만들기(그리디)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다. 이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열 을 만듭니다. 이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니 다.

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

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

direction = ""
result = list()

lt = 0
rt = N-1
last = 0

while lt<=rt:
    if nums[lt] > last:
        result.append((nums[lt], 'L'))
    if nums[rt] > last:
        result.append((nums[rt], 'R'))

    result.sort()

    if len(result) == 0:
        break
    else:
        direction += result[0][1]
        last = result[0][0]
        if result[0][1] == 'L':
            lt += 1
        else:
            rt -= 1
            
    result.clear()

print(len(direction))
print(direction)

- 답안에서는 이분탐색에서 사용했던 방식을 적용시켜 문제를 풀었다. (포인터 두 개 lt, rt 사용 / 인덱스 나타냄)

- 마지막의 값을 나타내는 last 변수의 값을 처음에는 0으로 초기화 시켜준다.

- nums[lt]가 last보다 크거나, nums[rt]가 last보다 클 때 → result에 튜플 형태로 (해당 값, 방향)을 추가해준다.

- result를 sort() 해준다. (이 때, 튜플의 첫번째 값을 기준으로 정렬이 진행된다)

- direction에 방향을 더해주고(문자 추가), last는 튜플의 첫번째 값을 넣어준다.

- 만약에 방향이 L이라면 → lt를 1 증가시켜주고 / R이라면 → rt를 1 감소시켜준다.

- result 리스트를 clear()로 초기화 시켜준다.

- lt가 rt보다 작거나 같을 동안만 while문을 반복시켜주고,

  result 리스트에 더이상 아무것도 들어오지 않아 len()이 0이 되었을 때 break문으로 while문의 반복을 멈춰준다.

- 최종적으로 direction의 길이(= 개수)와 direction의 문자열을 출력한다.