[이진탐색]-증가수열만들기(그리디)

증가수열만들기(그리기)

 

 

1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다.
이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열 을 만듭니다.

이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니 다.
예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다.
맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽끝에서5를가져와 2345증가수열을만들수있습니다.

 

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

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

 

▣ 입력예제 1

5
2 4 5 1 3

▣ 출력예제 1

4
LRLL

 

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

▣ 출력예제 2

3
LRR

 

 

나의 코드

from collections import deque

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

res=[]
dq=deque(arr)
res=[[0,'T']]

for _ in range(n):
    print(dq,res)
    if dq[0]<dq[-1] :# 왼쪽이 작은경우 
        if dq[0]>res[-1][0]: # 
            res.append([dq[0],'L'])
            dq.popleft()
        elif dq[-1]>res[-1][0]:
            res.append([dq[-1],'R'])
            dq.pop()

    elif dq[0] > dq[-1]:
        if dq[-1]>res[-1][0]:
            res.append([dq[-1],'R'])
            dq.pop()
        elif dq[0]>res[-1][0]:
            res.append([dq[0],'L'])
            dq.popleft()

print(len(res)-1)

for i in range(1,len(res)):
    print(res[i][1],end='')

음... 분기 처리 고려 부분이 보여 구현하긴 했는데 너무 코드가 난잡하고 가독성이 매우 좋지 않다..킁

뭐 그래도 출력값들은 모두 잘 나온다..!

 

 

우선 큰 흐름은 이렇다.

0. 최종 출력할 값들에 대한 데이터를 res에 저장한다.

1. 좌우 양끝의 대소를 비교

2. 작은 값에 대해 res의 가장 끝값과 비교하여 만족한 값을 Res에 넣는다.

 

 

 

정답 코드

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
        else:
            rt=rt-1
    tmp.clear()

print(len(res))
print(res)

정답 코드에서는 투포인터를 사용해서 구현을 했다.

우선 양 옆의 데이터를 모두 temp에 저장한뒤 정렬을 한다.

그 후 temp의 앞 데이터(더 작은수 )를 res에 추가한다.

 

가독성이 좋고 코드 작성시 실수도 줄어 들만한 좋은 코드인것 같다 기억해야 겠다 !