[Section04] Python 알고리즘 문제풀이 09~10

Q9. 증가수열 만들기(그리디) : 자연수로 구성된 N의 수열의 왼쪽이나 오른쪽 맨 끝 숫자를 가져와 가장 긴 증가수열을 만들어 출력

입력 :

N (3<=N<=100)

N개의 수

출력 :

증가수열의 길이

가져온 수의 방향에 따라 L, R 출력

 

[내가 쓴 코드]

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

pivot = 0  #가장 최근에 가져온 수 저장
count = 0  #수열의 길이
string = ""  #가져온 수의 방향 저장

while True :
    if pivot < a[0] and pivot < a[len(a) - 1] :  #기준수보다 양쪽수가 더 크면
        if a[0] < a[len(a) - 1] :  #왼쪽 수가 더 작으면 
            pivot = a.pop(0)  #왼쪽 수 빼기
            count += 1  #수열 증가
            string += "L"  #왼쪽 L
        else :  #오른쪽 수가 더 작으면 오른쪽 수를 빼고 count, string 업데이트
            pivot = a.pop(len(a) - 1)
            count += 1
            string += "R"
    elif pivot < a[0] :  #왼쪽에 수열로 넣을 수 있는 수가 있다면
        pivot = a.pop(0)
        count += 1
        string += "L"
    elif pivot < a[len(a) - 1] :  #오른쪽에 수열로 넣을 수 있는 수가 있다면
        pivot = a.pop(len(a) - 1)
        count += 1
        string += "R"
    else :
        break  #더이상 추가할 수가 없으면 break
            
print(count)
print(string)

 

[풀이 코드]

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

lt = 0  #왼쪽
rt = n - 1  #오른쪽
list = 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 += 1
        else :
            rt -= 1
    tmp.clear()
print(len(res))  #문자열의 길이 출력
print(res)

res의 길이로 출력하면 되는 것을 count를 따로 생성했다니.....

 

---

Q10. 역수열(그리디) : 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출력

입력 :

N (3<=N<=100)

N개의 수

출력 :

원래의 수열

 

[내가 쓴 코드]

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

b = [n+1] * n  #n+1로 이루어진 n개의 수를 저장

number = 1  #기준수

for x in a : 
    count = 0  #몇개의 수를 지나칠지 저장
    for i in range(n) :  #1~n 반복
        if b[i] > number :  #기준수보다 큰 수면
            count += 1  #count 증가하고 그 수를 지나침
            if count == x+1 :  #만약 count와 x의 값이 일치하게 되면
                index = i  #해당 인덱스를 저장하고 break
                break
    b[index] = number  #해당 index에 기준수 넣기
    number += 1  #기준수 증가

print(*b)  #완성된 list 출력

 

[풀이 코드]

n = int(input())
a = list(map(int, input().split()))
seq = [0]*n

for i in range(n) :
    for j in range(n) :
        if a[i] == 0 and seq[j] == 0 :  #빈 공간 확보 and 본인 자리가 비어있는지 확인
            seq[j] = i + 1
            break
        elif seq[j] == 0 :
            a[i] -= 1
for x in seq :
	print(x, end=" ")