[Python Algorithm] 그리디 알고리즘 - 증가수열 만들기(그리디)

> 이분 탐색(결정알고리즘) & 그리디 알고리즘 (그리디알고리즘 편)

 

📖 문제 :  증가 수열 만들기

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

 

 

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

 

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

 

입력예제 1

5
24513

 

출력예제 1

4
LRLL

 

입력예제 2
10
3 2 10 1 5 4 7 8 9 6

 

출력예제 2

3
LRR

 

 

import sys

n = int(input())
a = list(map(int, input().split()))
lt = 0
rt = n-1
tmp = []
result = ''
last = 0
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:
    	result = result + tmp[0][1]		#	튜플값을 넣는 방법
        last = tmp[0][0]
        if tmp[0][0] = 'L':
        	lt+=1
        else :
        	rt-=1
            
            
	tmp.clear()
print(len(result))
print(result)

 

⭐️ Point ! ⭐️

• tmp.append((a[lt], 'L'))
  튜플값을 리스트에 넣기.
  
  
• tmp.sort() 
  튜플로 이루어진 리스트에서 튜플의 앞의 값으로 정렬
  
  
• tmp[0][0], tmp[0][1]
  tmp리스트에서 0번째에 있는 튜플의 원소에 접근
  
  
• tmp.clear()
  리스트의 모든 원소 삭제
  
  

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이