[python] 코딩테스트 - 그리디(증가수열)

탱이나라 2022. 1. 28. 01:14
문제)
답안 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import sys
#sys.stdin=open("input.txt", "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=lt+1#왼쪽포인터 1 증가
        else:#오른쪽이라면,
            rt=rt-1#오른쪽 포인터 1 감소
   tmp.clear()#초기화
 
print(len(res))
print(res)

cs

 