[알고리즘] 증가수열 만들기

728x90

반응형

https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/dashboard

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의

 

해당 강좌에 포함되어 있는 문제다.

 

문제

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

 

 

파이썬의 데크를 사용해 그리디로 풀었다.

 

풀이는 

데크에 입력 수열이 담겨 있을때,

처음에 데크의 왼쪽 혹은 오른쪽에서 더 작은 수를 pop 하고 증가수열에 그 값을 저장한다.

그다음부터는 증가수열에 가장 마지막에 들어간 수를 last_num이라고 할 때, 데크의 제일 왼쪽과 오른쪽을 비교하고 둘 다 last_num보다 크다면 왼쪽 오른쪽 수 중 작은 수를 증가수열에 추가한다.

만약 두 수중 하나만 last_num보다 작다면 last_num보다 큰 수를 증가수열에 추가한다.

 

(추가될 땐 당연히 데크에서는 제거되어야 한다.)

 

만약 두 수 모두 last_num보다 작다면 더 이상 긴 증가수열이 만들어지지 않으므로 종료한다.

 

위 조건들을 반복하다가 데크에 마지막 하나의 숫자가 남았을 경우 last_num과 비교하고, last_num보다 크다면 left_pop을 한다.

 

정답

 

from collections import deque

def left_pop() :
    global ans_num, ans, deq, ans_list
    ans_num += 1
    ans += 'L'
    
    ans_list.append(deq.popleft())

def right_pop() :
    global ans_num, ans, deq, ans_list
    ans_num += 1
    ans += 'R'
    
    ans_list.append(deq.pop())

n = int(input())

deq = deque(list(map(int, input().split())))

ans_num = 0
ans = ""
ans_list = []

for i in range(n) :
    if i == 0 :
        if deq[0] < deq[-1] :
            left_pop()
        else :
            right_pop()

    else :
        if deq[0] == deq[-1] and deq[0] > ans_list[-1]:
            left_pop()
        elif deq[0] > ans_list[-1] and deq[-1] > ans_list[-1] :
            if deq[0] < deq[-1] :
                left_pop()
            else :
                right_pop()
        elif deq[0] > ans_list[-1] :
            left_pop()
        elif deq[-1] > ans_list[-1] :
            right_pop()
        else :
            break

print(ans_num)
print(ans)

---

if조건들만 잘 생각해 내면 쉽게 풀듯하다