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

사용 언어: Python3

문제

풀이

내 풀이

from collections import deque

N = int(input())
lst = list(map(int, input().split()))
lst = deque(lst)

cnt, ans = 0, ''
last = 0 # 이전에 선택한 항 (이 값보다는 커야지 선택된다)
while lst:
    if len(lst) == 1:
        if lst[0]>last:
            cnt, ans = cnt+1, ans+'L'
        break
    if lst[0]>last and lst[-1]>last:
        if lst[0]<lst[-1]:
            last, ans = lst.popleft(), ans+'L'
        else:
            last, ans = lst.pop(), ans+'R'
        cnt += 1
    elif lst[0]>last:
        tlastp = lst.popleft()
        cnt, ans = cnt+1, ans+'L'
    elif lst[-1]>last:
        last = lst.pop()
        cnt, ans = cnt+1, ans+'R'
    else:
        break

print(cnt)
print(ans)

다른 풀이 - 튜플 정렬

N = int(input())
lst = list(map(int, input().split()))

src, dest = 0, N-1
last, ans = 0, ''
tmp = [] # 정렬할 공간

while src <= dest:
    if lst[src]>last:
        tmp.append((lst[src], 'L')) # ✅ 튜플 형태로 넣기
    if lst[dest]>last:
        tmp.append((lst[dest], 'R'))
    if len(tmp) == 0: # ✅ tmp에 추가되는게 없으면 종료
        break
    tmp.sort() # ✅ 튜플의 첫번째 값 기준 정렬
    ans += tmp[0][1] # 정렬후 tmp[0]이 제일 작은 튜플값
    last = tmp[0][0]
    if tmp[0][1] == 'L':
        src += 1
    else:
        dest -= 1
    tmp.clear()

print(len(ans))
print(ans)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기