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

입력

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

 

출력

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

 

문제풀이

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 += 1
    else:
      rt -= 1
  tmp.clear()

print(len(res))
print(res)