9. 증가 하는 수열 만들기

문제

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

 

 

 

문제풀이

import sys
sys.stdin=open("input.txt", "r")

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


last =0
lt = 0
rt = n-1
res =""
tmp =[]

while lt<=rt:
    if p[lt]>last:
        tmp.append((p[lt], 'L'))
    if p[rt]>last:
        tmp.append((p[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)

 

 

해설

last 용도 : 수열을 만들기 위해서 이전 값보다 큰 값을 넣어야 하는데, 

                 "이전 값보다 커야지"할 때의 이전값을 의미한다. 

 

전체 사이클

tmp에 a[lt] 1개가 들어 갈 수도 있고,

tmp에 a[rt] 1개가 들어 갈 수도 있다.

tmp에 a[lt]와 a[rt] 2개가 들어 갈 수도 있다.

 

tmp리스트를 정렬했는데,

tmp에 아무것도 들어 가지 않는 경우는

더 이상 수열을 만들 수 없으므로 반복문을 종료

 

else:

tmp에 1개 또는 2개가 들어갔든

맨 앞쪽의 요소(tmp[0])의 두번째 값(tmp[0][1])을 res에 저장한다.

 

※만약에 tmp에 좌측값과 우측값 1개개씩 값이 들어 갔다면, 둘 중 한쪽만 처리되고, 한쪽만 +1 증가 되므로

 

처리 되지 않은 다른 한쪽은 인덱스 값이 변화가 없으므로 while반복시 이전 값이 재사용된다.