파이썬 알고리즘-30 (탐색, 그리디) 증가수열 만들기

30.증가수열 만들기(그리디)
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

내 코드

from collections import deque

n=int(input())
lst=list(map(int, input().split()))
lst=deque(lst)
cnt=0
ep=0
lr=''
while ep<lst[0] or ep<lst[-1]:
    if len(lst)==1 and lst[0]>ep:
        cnt+=1
        lr+='L'
        break
    if len(lst)==2 and ep<max(lst):
        
    if lst[0]<lst[-1] and lst[0]>ep:
        ep=lst[0]
        lst.popleft()
        cnt+=1
        lr+='L'
    elif lst[-1]<lst[0] and lst[-1]>ep:
        ep=lst[-1]
        lst.pop()
        cnt+=1
        lr+='R'
    else:
        break

print(cnt)
print(lr)

코드 완성도 못했다. 내용도 쓰레기

풀이

n=int(input())
a=list(map(int, input().split()))
lt=0
rt=n-1
last=0
res=""
tmp=[]
while lt<=rt:
    if a[lt]>last:
        tmp.append((a[lt], 'L'))
    if a[rt]>last:
        tmp.append((a[rt], 'R'))
    tmp.sort()
    if len(tmp)==0:
        break;
    else:
        res=res+tmp[0][1]
        last=tmp[0][0]
        if tmp[0][1]=='L':
            lt=lt+1
        else:
            rt=rt-1
    tmp.clear()

print(len(res))
print(res)

반성점

• 모르는 개념은 없었는데 풀이 방법이 생각이 안난다.

배운 것

• 내가 노답이라는 것ㄱ