무지의 먹방라이브

minjun kim·2024년 4월 16일

RE 그리디

Check Point !
( 해당사항 ✓체크 )

막힘 없이 수월하게 풀린 문제인가?

1시간이내로 풀렸던 문제인가?

1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가? ✅

시간을 써도 도무지 풀 수 없는 문제인가?

솔루션을 찾아봤는가? ✅

난이도 체감

최상

상

중

하 ✅ (??)

<이해도>

완벽히 이해

다소 헷갈리는 부분들이 있음 ✅

이해 못함

<덧붙일 말>
나동빈책에 실려있는 내용을 이해하려면 우선순위큐를 이해해야해서 나주에 이해하고 다시돌아와서 풀어보자.

모듈중에 operator중 itemgetter 부분

코테를 풀기전, 해당 방법을 풀기위해 설계를 미리 하고 들어가고, 태케를 미리 꼼꼼히 생각해보자.

아직 변수를 바꿔가며 풀어가는것이 정확하게 적용하는게 어리숙해보인다..
잘 적용하며 모든 문장에 주석을 달며 천천히 풀어보자.

우선순위큐를 이용1

큐는 선입선출 FIFO로 먼저들어온것이 먼저나가는 구조로 되어있지만
우선순위 큐는 들어오는 순서는 상관없지만, 값이 적은 것부터 나가게 된다.

클래스 임포트
우선 PriorityQueue 클래스는 queue 내장 모듈에서 제공되기 때문에 파이썬만 설치되어 있으면 별다른 추가 설치없이 임포트할 수 있다.

from queue import PriorityQueue

우선순위 큐 생성

PriorityQueue() 생성자를 이용해서 비어있는 우선순위 큐를 초기화할 수 있습니다.

que = PriorityQueue()

우선순위 큐의 디폴트 사이즈는 무한대입니다. 만약에 특정 최대 크기를 가진 우선순위 큐가 필요하다면 maxsize를 넘기면 됩니다.

que = PriorityQueue(maxsize=8)

우선순위 큐에 원소 추가

PriorityQueue 클래스의 put() 메서드를 이용하여 우선순위 큐에 원소를 추가할 수 있습니다.

que.put(4)
que.put(1)
que.put(7)
que.put(3)

우선순위 큐에 원소 삭제

PriorityQueue 클래스의 get() 메서드를 이용하여 우선순위 큐에 원소를 삭제할 수 있습니다.

print(que.get())  # 1
print(que.get())  # 3
print(que.get())  # 4
print(que.get())  # 7

get() 메서드는 삭제된 원소를 리턴하기 때문에, 위와 같이 출력을 해보면, 크기 순서대로 원소가 삭제됨을 알 수 있다.

정렬 기준 변경

만약 단순 오름차순이 아닌 다른 기준으로 원소가 정렬되기를 원한다면, (우선순위, 값)의 튜플의 형태로 데이터를 추가하고 제거하면 됩니다.

que.put((3, 'Apple'))
que.put((1, 'Banana'))
que.put((2, 'Cherry'))

print(que.get()[1])  # Banana
print(que.get()[1])  # Cherry
print(que.get()[1])  # Apple

get() 과 ,put()의 경우 O(logN)의 시간을 가진다.

다양한 기준으로 정렬하려면? ― operator.itemgetter

from operator import itemgetter

students = [
    ("jane", 22, 'A'),
    ("dave", 32, 'B'),
    ("sally", 17, 'B'),
]

result = sorted(students, key=itemgetter(1))
print(result)

실행하여 출력해 보면 다음과 같이 나이 순서대로 정렬한 것을 확인할 수 있다.

[('sally', 17, 'B'), ('jane', 22, 'A'), ('dave', 32, 'B')]

풀이1)

코드 1

from operator import itemgetter

def solution(food_times,k):
    arr = []
    n = len(food_times)
    for i in range(n):
        arr.append((food_times[i],i+1))
    
    arr.sort()
    
    pretime = 0
    for i, letter in enumerate(arr):
        diff = letter[0]- pretime
        
        if diff != 0:
            spend = (diff * n)
            
            if k >= spend:      
                k -= spend
                pretime = letter[0]
            else:
                k %= n
                sublist = sorted(arr[i:], key = itemgetter(1))
                return sublist[k][1]
        n -= 1
        
    return -1

from operator import itemgetter
def solution(foodtimes, k):
    result = 0
    arr = [] # 빈 배열선언 
    n = len(foodtimes) # foodtimes 길이, 총개수
    for i in range(n): # 모든 배열의 길이를 돌며,
        arr.append((foodtimes[i],i+1)) #  foodtimes , 음식의 순번 으로 튜플을 배열에 저장함.
    
    arr.sort() # foodtimes를 기준으로 정렬
    
    preval = 0 
    for i, letter in enumerate(arr): # i가 필요한 이유는 k보다 큰 값이 할당 되었을때 해당 기준으로 자르기 위함. \
                                        # 따라서, enumerate로 arr 설정. ex. (0,(3,1)) 
        diff = letter[0] - preval # 현재 높이 값
        if diff != 0:  # 높이가 다르다면 진행 같디면, 더 앞에서 제거했기때문에 또 연산할 필요가 없음.
            spend = diff * n  # 빼야할 값
            if k >= spend: # 남은값이 더 크다면 정상적으로 진행
                k -= spend # 값 빼줌
                preval = letter[0] # 전의 값을 높이 값을 저장해두고 diff를 바꿔줌.
            else: # 남은 값인 k보다 빼야할 spend의 값이 크다면 ?
                k %= n # 나머지를 통해 순번위치를 지정 
                leftarr = sorted(arr[i:], key = itemgetter(1)) # 남은 배열 / 위에서 정의한 순번을 가지고 재정렬
                return leftarr[k][1] # (5,2)(6,4)(5,5) 순으로 정렬된 값을 첫번째배열의 4를 출력.
        n -= 1 # 밑값을 하나씩 줄여감.
    
    return -1 # 만약 배열을 다돌았는데 값이 없다면 총 foodtime보다 k값이 큰것 -1을 출력


print(solution([3,1,2],5))