[Algorithm] 증가수열 만들기 (그리디)

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

양쪽 끝을 비교해야하므로 lt와 rt 변수를 만들어 각각 맨 왼쪽 인덱스, 맨 오른쪽 인덱스를 가르킨다.
last 변수는 증가수열의 마지막 수를 가르킨다.
따라서 a[lt]나 a[rt]는 last보다 커야 다음 증가수열이 될 수 있다.
last보다 크다는 조건이 성립되면 tmp라는 리스트에 튜플 형식으로 값과 'L' 또는 'R'을 넣는데, 여기서 a[lt]면 'L'을, a[rt]면 'R'을 넣는다.
tmp에 튜플을 오름차순으로 정리면 맨 위의 값이 a[lt]와 a[rt] 중 작은 값이 될테고, 혹은 a[lt] 만 있거나 a[rt] 만 있을 수도 있다.
만약 tmp에 값이 없다면 더이상의 증가수열이 만들어질 수 없다는 것이니 반복문을 나온다.
아무튼, 오름차순의 맨 첫번째 자료를 증가수열에 넣고 그게 왼쪽 자료이면 lt+=1을, 오른쪽 자료이면 rt-=1을 한 후 tmp를 clear 시켜서 반복한다.

<모범답안>

n = int(input())
a = list(map(int, input().split()))

lt = 0
rt = n-1

last = 0
tmp = []
s = ''

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:
        s = s + tmp[0][1]
        last = tmp[0][0]
        if tmp[0][1] == 'L':
            lt += 1
        else:
            rt -= 1
    tmp.clear()

print(len(s))
print(s)