.PNG)
30. 증가수열 만들기(그리디)
1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다.
이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열
을 만듭니다. 이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니
다.
예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다.
맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4,
왼쪽 끝에서 5를 가져와 2 3 4 5 증가수열을 만들 수 있습니다.
▣ 입력설명
첫째 줄에 자연수 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
<내 풀이>
모든 경우의 수를 다 찾아서 풀었는데 이 접근법이 맞는지 모르겠다
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
k=[]
s=[]
cnt=0
if a[0]<a[-1] :
k.append(a.pop(0))
s.append('L')
cnt+=1
else:
k.append(a.pop(-1))
s.append('R')
cnt+=1
for _ in range(n) :
if a[0]<k[-1] and a[-1]<k[-1] :
break
elif a[0]>k[-1] and a[-1]>k[-1] :
if b.index(a[0])-b.index(k[-1]) < b.index(a[-1])-b.index(k[-1]):
k.append(a.pop(0))
s.append('L')
cnt+=1
else :
k.append(a.pop(-1))
s.append('R')
cnt+=1
elif a[0] > k[-1]:
k.append(a.pop(0))
s.append('L')
cnt+=1
elif a[-1] > k[-1]:
k.append(a.pop(-1))
s.append('R')
cnt+=1
print(cnt)
for i in s :
print(i, end='')
<풀이>
- 이분검사를 활용 - lt랑 rt 자주 쓰인다
- (1) 첫 항에서 lt와 rt중 작은 값을 가져오기
- 그리고 가져온 값의 마지막 하나는 상시 기억되어야하므로
리스트는 아니고 last=0이라는 값에 저장시켜준다 - 또 문자열 넣어줄 때 리스트 굳이 생성안하고 '' 만 생성해도 된다
n=int(input())
a=list(map(int,input().split()))
lt=0
rt=n-1
last=0
res=''
tmp=[]
#여기에 last보다 큰 lt 혹은 rt 혹은 둘다 다 데려와서 뭐가 더 작은지 판별
while lt<=rt:
if a[lt]>last:
tmp.append((a[lt], 'L'))
if a[rt]>last :
tmp.append((a[rt], 'R'))
tmp.sort() #정렬해서 tmp의 첫항을 수열의 다음항으로 결정, last보다 크면서 lt,rt중 가장 작은값
if len(tmp)==0:
break #lt랑 rt랑 둘다 마지막항보다 작아져버림
else :
res=res+tmp[0][1] #[0]은 tmp의 가장 첫번째 [1]은 'L','R'
last=tmp[0][0]
if tmp[0][1]=='L':
lt+=1
else:
rt-=1
tmp.clear()
print(len(res())
print(res)<반성점>
- 나는 s=[] 를 만들어서 문자열더해주고 수열의 길이를 구하는 cnt도 따로 만들어서 구했는데 그냥 len(s)하면 수열의 길이였던 것이다
- 강사님과 같이 사고하는 방법도 익숙해져 놓자. 복습할 때 강사님 풀이 위주로 보면서 사고력을 길러보자
- append할 때 두개 이상의 요소를 한번에 튜플로 저장, 리스트로 저장해서 활용하는 방법 자주 사용하자
- lt와 rt개념 자유자재로 활용하자
<배운 점>
-
문자열 넣어줄 때 리스트 굳이 생성안하고 '' 만 생성해도 된다
-
tmp=[(a,0), (b,1), (c,2)] 일때
tmp[0][0]은 a, tmp[0][1]은 0 => 이 방법 자주 used된다 -
가져온 값의 마지막 하나는 상시 기억되어야하므로
리스트는 아니고 last=0이라는 값에 저장하는 방법도 존재, 굳이 k 리스트 만들어서 k[-1]로 계속해서 갱신 안해도 되고
