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

(문제) 증가수열 만들기(그리디)

---

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

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

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

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

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

입력설명

첫째 줄에 자연수 N(3<=N<=100)이 주어집니다.

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

출력설명

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

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

테스트케이스

입력예제	출력예제
5 2 4 5 1 3	4 LRLL
5 1 3 5 2 4	4 LLRL
10 3 2 10 1 5 4 7 8 9 6	3 LRR

---

해결방법

문제는 증가 수열을 구하는 것이며 N개로 구성된 수열이라고 함으로 1~N 까지 만들기 때문에, 첫 비교를 0으로 시작하기 위해 last 라는 변수를 생성하여 0으로 초기화 한다.

“L” 혹은 “R”을 저장할 수 있는 word 변수를 추가 한다.

lt : 시작위치 와, rt : 끝 위치를 인덱스로 잡아 놓는다.

만약 이 lt 가 rt 보다 작을 때 무한 반복을 한다.

이 아래 있는 과정은 일정 조건이 충족하지 않는 이상 무한 반복을 할 것이다.

그 후, temp라는 리스트를 생성하여 값이 들어있는 리스트의 맨 왼쪽 값과 맨 오른쪽 값 중, last 보다 큰 값을 temp라는 리스트에 대입한다.

대입할 때, 왼쪽것을 대입할 때는 튜플로 (값, “L”) 로 대입하고, 오른쪽 것을 대입할 때는 튜플로 (값, “R”) 로 대입합니다.

그 후, temp를 정렬 시킨다.

정렬을 시켜야 그 다음 위치에 들어갈 수열이라는 것을 알 수 있기 때문이다.

만약에 temp 라는 리스트에 값이 있으면 가장 첫번째 인덱스에 있는 값과 위치를 값은 last에 대입하고 위치 즉, “L” 혹은 “R”은 word에 추가한다.

추가 할 때 만약에 “L”을 추가하면 lt에 + 1을 하고, “R”을 추가하면 rt - 1로 rt를 줄여 준다!

만약 temp 라는 리스트에 값이 없으면 이 반복문을 종료한다.

---

코드

n = int(input())

arr = list(map(int, input().split()))

last = 0

lt = 0
rt = n-1

temp = []

word = ""

while lt < rt:
    if last < arr[lt]:
        temp.append((arr[lt], "L"))
    if last < arr[rt]:
        temp.append((arr[rt], "R"))
    temp.sort()

    if temp:
        word = word + temp[0][1]
        last = temp[0][0]
        if temp[0][1] == 'L':
            lt = lt + 1
        else:
            rt = rt - 1
        temp.clear()
    else:
        break

print(len(word), word, sep='\n')