요즘 코테에는 그리디와 구현문제가 정말 많다.
특히 뭔가가 많은 순서대로, 적은 순서대로 우선순위를 세워서 접근해야 하는 문제가 많다.
특히 최근 heapq가 유용한 문제들을 많이 접한 것 같아서 각 잡고 쭉 풀면 감을 살릴 수 있도록 정리해보았다.
백준 1100번
어려울 수 있는 점
주어지는 강의의 시작과 끝 시간 중에 어떤 것끼리 비교해야 하는지, 또한 둘 중 어떤 시간을 기준으로 정렬을 해놓고 시작해야는지 헷갈릴 수 있다.
솔루션
정렬
시작시간을 1위 정렬순위, 끝나는시간을 2위 정렬순위로 두고 정렬을 하고 들어간다. 끝나는 시간을 기준으로 정렬하면 곤란해지는 이유는 솔루션의 접근 방법을 보며 유추할 수 있다. 시작시간이 빠른 녀석들부터 비교해야, 시작시간과 끝나는시간 사이의 간격이 짧은 강의부터 방을 찾아줘야 최소의 강의실 개수를 찾을 수 있기 때문이다.
힙큐 = 강의실
강의 ㄱ,ㄴ,ㄷ가 있다고 가정하면, ㄱ이 끝나는 시간은 ㄴ이 시작하는 시간보다 짧아야 같은 강의실을 쓸 수가 있다. 같은 강의실을 쓸 수 있으면 힙큐에 들어있던 ㄱ의 자리를 ㄴ이 대체할 수 있다. 같은 강의실을 못 쓴다면 힙큐에 새로운 강의실을 만들어주듯이 ㄴ을 넣는다고 생각해야 한다.
최종적으로 힙큐의 길이가 필요한 강의실의 최소 갯수가 된다.
#11000번
import heapq
import sys
input = sys.stdin.readline
N = int(input())
time = []
for _ in range(N):
time.append(list(map(int, input().split(' '))))
time.sort(key = lambda x: (x[0], x[1]))
heap = [time[0][1]] #첫번째 원소의 끝나는 시간
for i in range(1,N):
if heap[0] <= time[i][0]: #시간 비교, 강의실 힙타겟의 끝나는 시간이 시간표비교 타켓보다 같거나 작거나 같으면 꺼낸다.
heapq.heappop(heap)
heapq.heappush(heap, time[i][1]) #끝나는 시간을 넣어줌
print(len(heap))정렬 기준이 여러개인 힙큐 문제
[프로그래머스]베스트 앨범
보자마자 우선순위 힙큐를 써야겠다고 생각이 나던 문제이다. 주의해야 할 점은 우수록해야 하는 원소의 기준이 3가지이다.
1.속한 노래가 많이 재생된 장르를 먼저 -> a
2.장르 내에서 많이 재생된 노래를 먼저 -> b
3.장르 내에서 재생횟수가 같은 노래 중에서 고유번호가 낮은 노래를 먼저->c
어려울 수 있는 부분
처음에는 a,b,c를 모두 내림차순으로 정렬했다. 하지만 조건을 잘못 본 걸 깨닫고 a,b는 내림차순, c는 오름차순으로 정렬했다. 힙큐가 유용한 이유가 바로 이부분이라고 느꼈다.
솔루션 - 힙 큐 내림차순, 오름차순
힙 큐는 디폴트로 오름차순 정렬이 된다. 그렇기 때문에 내림차순을 하고 싶다면, 앞에 -를 붙이고 나중에 pushpop으로 값을 활용할 때 -를 다시 붙이는 등 값을 원래 값으로 복구해주어야 한다.
h.append([-d,-plays[j],j])내 코드의 아쉬운 부분
빨리 푸는 걸 목표로 했기 때문에 아무래도 해쉬값을 지저분하게 이용했다. 코테 스터디의 다른 분은 굉장히 깔끔하게 2차원으로 해결하셨다. 사실 해쉬라는 키워드가 힌트로 있었는데 몰랐다. 누가봐도 해쉬였기 때문에 큰 힌트는 아니었던 문제.
import heapq
def solution(genres, plays):
answer = []
h = []
#장르 카운팅 및 장르 별 총 재생수
genres_type = [] #genres_type = ["classic","pop"]
sum_dict = {} #sum_dict = {"pop":3100, "classic":1450}
for i in range(len(genres)):
if genres[i] not in genres_type:
genres_type.append(genres[i])
sum_dict[genres[i]] = plays[i]
else:
sum_dict[genres[i]] += plays[i]
genres_type.sort()
#힙 생성
for j in range(len(plays)):
g_type = genres[j]
d = sum_dict[g_type]#장르 총 플레이수
h.append([-d,-plays[j],j]) #장르 총 플레이수, 재생수는 내림차순 고유번호 고유번호만 오름차순
h.sort(key = lambda x:(x[0], x[1], x[2]))
heapq.heapify(h)
#앨범 빈도수 카운팅용
album_count = {} #album_count = {"3100":0, "1450":0}
for key in sum_dict:
album_count[sum_dict[key]] = 0
#앨범 도출 시작
for i in range(len(h)):
l = heapq.heappop(h)
_genre,num = -l[0],l[2]
count = album_count[_genre]
if(count < 2):
album_count[_genre] += 1
answer.append(num)
return answer