[백준] 1766번: 문제집 - 파이썬

문제보기

https://www.acmicpc.net/problem/1766

1766번: 문제집

 

 

 

 

 

 

---

 

풀이 및 코드

 

해당 문제는 heap을 사용해 푸는 문제로 solved.ac에 골드2로 랭크되어 있다.

 

 

 

필자는 먼저 두개의 dictionary와 하나의 배열을 만들었다.

relationDict = {i: [] for i in range(1,n+1)}
hardCountDict = {i: 0 for i in range(1,n+1)}
easier = []

relationDict는 input으로 들어온 관계를 저장한 값으로 5보다 4를 먼저 풀어야 한다면, relationDict[4] = [5]로 저장되도록 했다. 배열로 저장한 이유는 4보다 어려운 문제가 1개가 아닐 수 있기 때문에 배열로 저장했다.

hardCountDict는 해당 문제를 풀 때 이전에 몇개를 더 먼저 풀어야 하는 지를 저장했다. 예를 들어 5를 풀기 위해 3, 4을 먼저 풀어야 한다면 hardCountDict[5] = 2가 된다.

easier은 사전에 풀게 없는 문제들을 저장했다. 이것을 따로 저장한 이유는 easier에서 가장 작은 수를 하나씩 골가가며 문제집을 구성할 것이다. 한번에 sort하고 앞에서부터 하나씩 빼면 되겠다라고 생각할 수도 있겠지만, 문제를 풀어가면서 easier에 새로운 값이 추가 될 수도 있다. 앞의 예의 경우 3, 4을 풀었다면 5번은 이제 사전에 풀어야 할 문제가 없어진다. 이럴 경우 easier에 새로운 값이 추가되게 된다. 중요한 점은 추가될 때마다 새로 sort를 해준다면 너무 오랜 시간이 걸리기 때문에 이를 방지하고자 heap 자료구조를 활용해야 한다.