Algorithm - 증가수열 만들기(그리디)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[증가수열 만들기]

 

1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어진다.

이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열을 만든다.

이 때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거된다.

 

예를들어, 2 4 5 1 3이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4이다.

맨 처음 왼쪽 끝에서 2, 그 다음 오른쪽 끝에서 3, 그다음 맨 왼쪽 끝에서 4, 그다음 맨 왼쪽 끝에서 5를 가져와서 2 3 4 5의 증가수열을 만들 수 있다.

 

 

*입력 설명

첫 번째 줄에 자연수 N(3 ≤ N ≤ 100)이 주어진다.

두 번째 줄에 N개로 구성된 수열이 주어진다.

 

*출력 설명

첫 번째 줄에 최대 증가수열의 길이를 출력한다.

두 번째 줄에 가져간 순서대로 왼쪽 끝에서 가져갔으면 'L', 오른쪽 끝에서 가져갔으면 'R'을 써서 문자열을 출력한다.

단, 마지막에 남은 값은 왼쪽 끝으로 생각한다.

 

 

---

 

 

풀이(Python)

답안

import sys 
sys.stdin = open('AA/input_30.txt', 'rt')

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)

'''
출력 :
3
LRR

'''

 

input_30.txt(입력)

10
3 2 10 1 5 4 7 8 9 6

 

 

중요내용

1. 변수 res는 문자열을 저장하는 용도로 사용된다.
2. 리스트 안의 데이터가 튜플 자료형인 경우에는 sort() 함수가 튜플 자료형의 첫 데이터를 기준으로 정렬을 한다.
3. tmp[0][1]는 리스트 tmp 안에 있는 맨 앞의 튜플에서 첫 번째 데이터를 읽어오는 코드이다.