[인프런] 증가수열 만들기

---

문제설명

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

입력조건

• 첫째 줄에 자연수 N(3 <= N <= 100)이 주어진다.
• 둘째 줄에 N개로 구성된 수열이 주어진다.

출력조건

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

사고과정

• 투 포인터를 활용해서 푸는 접근 방식은 맞았다.. 그러나 중간에 왼쪽 또는 오른쪽에서 빼낸 수열이 증가수열이 아니게 되었을 때 체크를 해야 하는데 이를 구현하지 못했다..
• 풀이를 보니 매번 단계에서 왼쪽/오른쪽에서 빼낸 수열과 방향을 담고 정렬하는 리스트를 새롭게 정의했다. 그리고 이 때, 매 단계마다 이 리스트에 아무것도 들어있지 않으면 그 때는 더이상 증가수열이 만들어지지 않는다는 것을 의미한다! 또 둘 중 한쪽만 증가수열 만드는 것이 가능하진다고 하더라도 새롭게 정의하고 정렬한 리스트에 담아놓기 때문에 처리가 가능하다.. 왼쪽/오른쪽에서 빼낸 수열을 담는 리스트를 새롭게 정의하는 게 핵심! 
• 그리고 매번 단계가 끝날 때마다 list.clear() 함수로 다시 리스트를 빈 것으로 초기화해주어야 하는 것도 인상적이었다!
• 새롭게 정의하는 리스트를 우선순위 큐로 정의해보는 다른 시도를 해보려 했지만 리스트를 참조하는 횟수가 2번 이상이기 때문에 우선순위 큐는 적절하지 못하다고 판단했다.

풀이(스스로 못 푼 풀이)

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()
    # 왼쪽/오른쪽 아무것도 들어가지 않았으면 break
    if len(tmp) == 0:
        break
    else:
        res += tmp[0][1]
        last = tmp[0][0]
        if tmp[0][1] == 'L':
            lt += 1
        else:
            rt -= 1
    # tmp 빈리스트로 초기화
    tmp.clear()
print(len(res))
print(res)