[Section04] Python 알고리즘 문제풀이 07~08

Q7. 창고 정리 : L개의 자연수를 입력받아 높이가 가장 큰 수는 -1을 가장 작은 수는 +1을 조정 횟수만큼 반복하여 최종 적으로 가장 큰 수와 가장 작은 수의 차이를 출력

입력 :

L (1<=L<=100)

L개의 수

M (1<=M<=1,000)

출력 : 가장 큰 수와 작은 수의 차이

 

[내가 쓴 코드]

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

for i in range(m) :  #조정 횟수만큼 반복
    ih = a.index(max(a))  #현재 가장 큰 수의 index를 ih에 저장
    il = a.index(min(a))  #현재 가장 작은 수의 index를 il에 저장
    a[ih] -= 1  #가장 큰 수 -1
    a[il] += 1  #가장 작은 수 +1
    
print(max(a)-min(a))  #최종적으로 가장 큰 수 - 가장 작은 수 출력

 

[풀이 코드]

L = int(input())
a = list(map(int, input().split()))
m = int(input())

a.sort()

for _ in range(m) :
    a[0] += 1
    a[L-1] -= 1
    a.sort()

print(a[L-1]-a[0])

나는 변수를 만들어서 매번 가장 큰 수와 작은 수의 index를 받아왔는데 풀이는 sort로 가장 큰 수와 가장 작은 수의 위치를 고정해두는 방법을 사용함

 

---

Q8. 침몰하는 타이타닉(그리디) : 총 무게가 Mkg이하이고 최대 2명만 탈 수 있는 구명보트를 사용하여 N명의 승객을 모두 탈출하기 위한 구명보트의 최소개수 출력

입력 :

N (5<=N<=1000) M (70<=M<=250)

N명의 몸무게

출력 : 구명보트 개수

 

[내가 쓴 코드]

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

a.sort(reverse=True)  #무게가 많이 나가는 순서대로 정렬
count = 0  #사용한 구명보트 개수

while a :  #몸무게 리스트에 사람이 존재하는 동안 반복
    pivot = a.pop(0)  #첫번째 사람 빼기
    
    for i in range(len(a)) :  #몸무게 리스트에 남은 사람만큼 반복
        if pivot + a[i] <= m :  #만약 첫번째 + 그 다음 사람 <= m 이라면
            a.pop(i)  #두번째 사람 제거
            count += 1  #구명보트 사용
            break  #반복문 탈출
    else :  #if문에 부합하는 사람이 없다면 혼자 탑승
        count += 1
        
print(count)

 

[풀이 코드]

#from collections import deque

n, limit = map(int, input().split())
p = list(map(int, input().split()))
 
p.sort()
cnt = 0

while p :
    if len(p) == 1 :
        cnt += 1
        break
        
    if p[0] + p[-1] > limit :
        p.pop()
        cnt += 1
    else :
        p.pop(0)  #p.popleft() => deque 자료구조 사용
        p.pop()  
        cnt += 1
        
print(cnt)

 

정렬을 하긴 했는데 최대한 구명보트 총 무게에 가깝게 하려는 의도로 반복문 사용