[파이썬 알고리즘 문제풀이] - Section4 / 이분탐색(결정알고리즘) & 그리디 알고리즘 - 9

🎈 증가수열 만들기(그리디)

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

예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다.
맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽 끝에서 5를 가져와 2 3 4 5 증가수열을 만들 수 있습니다.

▣ 입력설명
첫째 줄에 자연수 N(3<=N<=100)이 주어집니다.
두 번째 줄에 N개로 구성된 수열이 주어집니다.

▣ 출력설명
첫째 줄에 최대 증가수열의 길이를 출력합니다.
두 번째 줄에 가져간 순서대로 왼쪽 끝에서 가져갔으면 ‘L', 오른쪽 끝에서 가져갔으면 ’R'를 써간 문자열을 출력합니다.(단 마지막에 남은 값은 왼쪽 끝으로 생각합니다.)

▣ 입력예제 1
5
2 4 5 1 3

▣ 출력예제 1
4
LRLL

▣ 입력예제 2
10
3 2 10 1 5 4 7 8 9 6

▣ 출력예제 2
3
LRR

import sys
# sys.stdin = open("input.text", "rt")

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

left = 0
right = N-1

last = -1
res = ""
cnt = 0

temp = []

while left <= right:
    if data[left] > last:
        temp.append((data[left], "L"))
    if data[right] > last:
        temp.append((data[right], "R"))
    
    temp.sort()  #값을 통해 정렬

    if len(temp) == 0: #들어온게 없으면 더이상 안되는거잖아
        break

    res += temp[0][1]
    last = temp[0][0]
    cnt += 1
    if temp[0][1] == "L":
        left += 1
    else:
        right -= 1

    temp.clear()

print(cnt)  #len(res) 출력해도 됨!
print(res)

🎃 코멘트
temp라는 메서드에 값과 방향을 같이 저장해서 쉽게 정렬하는 방법을 사용했다.
양 사이드에서 접근하되, 비교 값이 두개라면 튜플 형태로 저장해놓고 기준 하나를 정렬해놓고 비교하면 편하다. 이 방법 숙지