[Python] 그리디 문제 풀이 정리(2)

 

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

# 정답 풀이
from collections import deque
N=int(input())

A=[]
num={}

for _ in range(N):
    A.append(input())

for i in A: # 각 문자열에서
    for j in range(len(i)): # 문자열 알파벳 조사
        k = 10**(len(i)-j-1) # 알파벳 자릿수
        if i[j] in num: # dict에 있으면 더하고
            num[i[j]]+=k
        else: # 없으면 추가
            num[i[j]]=k

sorted_dict = sorted(num.items(), key = lambda item: item[1], reverse = True)
# 자릿수 순으로 정렬
ans = 0
n=9
for i in sorted_dict:
    ans+=i[1]*n
    n-=1

print(ans)

• 바로 어려워졌다.
• 핵심은 num dictionary에 각 알파벳의 자릿수를 더하여 정렬하는 것! 예를 들어 ABA 문자열이 있다면 dict의 A key에는 101이 저장된다.
• 이렇게 저장된 Value를 내림차순으로 정렬한 후 9~1을 곱하여 더해준다.

 

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

# 내 풀이
N, K = map(int, input().split())
A = []
for _ in range(N):
    A.append(list(map(int, input().split()))) #[정보 M, 가격 V]

A.sort(key=lambda x : -x[1]) # 가격 기준 내림차순 정렬
ans = 0
B = []

for _ in range(K):
    B.append(int(input()))

B.sort()
for c in B:
    for i in A:
        if i[0]<=c:
            ans+=i[1]
            i[0]=100000001
            break

print(ans)

• 시간초과 날 것 같긴했음^^ 근데 어떻게 줄이지...

# 정답풀이
import sys
import heapq

N, K = map(int, sys.stdin.readline().split())
jew = []
for _ in range(N):
    heapq.heappush(jew, list(map(int, sys.stdin.readline().split())))
bags = []
for _ in range(K):
    bags.append(int(sys.stdin.readline()))
bags.sort()

answer = 0
tmp_jew = []
for bag in bags:
    while jew and bag >= jew[0][0]:
        heapq.heappush(tmp_jew, -heapq.heappop(jew)[1])
    if tmp_jew:
        answer -= heapq.heappop(tmp_jew)
    elif not jew:
        break
print(answer)

• heap구조를 이용한다.
• 가방의 용량을 오름차순으로 정렬하고, 가방에 담을 수 있는 모든 보석을 찾기 위해 최소힙을 이용한다. 즉 -를 이용해서 최소힙을 이용한다.
  • 만약 bag의 무게가 보석의 무게보다 크다면, tmp_jew에 최소힙 형태로(음수로 저장)보석의 가치를 저장한다.
  • 이렇게 되면 가장 높은 가치의 보석을 최소로 인식하고, pop()할때 가장 먼저 꺼내진다!
• 보석을 다 돌았으면, 보석중 가장 가치가 높은 보석을 찾기 위해 최대힙을 이용한다.
• answer에는 tmp_jew에 저장된 보석중 가장 위의 값을 꺼낸다.(가장 높은 가치의 보석) 음수로 저장되어 있으므로 한번 더 -를 붙여 answer에 추가한다.
• tmp_jew를 초기화할 필요는 없다. bags를 정렬했으므로 다음에 오는 가방은 무조건 더 많이 수용할 수 있으므로!
• -를 붙여 힙을 다루는 것은 늘 어렵다...

 

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

# 정답 풀이
import sys
N= int(input())

A = list(map(int, input().split()))
A.sort()

last = 0
for i in A:
    if i<=last+1:
        last+=i
        continue
    else:
        break

print(last+1)

• https://aerocode.net/392#%EA%B0%9C%EC%9A%94

백준 2437 풀이 및 해설

• 정말 깔끔한 설명! 위 설명을 참고했다...
• 내가 만약 이전 무게 추를 이용해 [1,5] 구간을 잴 수 있다면, 이후 내가 4를 추가했을 때 [1+4,5+4] 구간을 잴 수 있는 것이다.
• 만약 다음 추가되는 무게추가 7인 경우, 7>5+1이므로 잴 수 없다.

 

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

# 정답 풀이
S = list(input())
T = list(input())

while T:
    if T[-1]=='A':
        T.pop()
    elif T[-1]=='B':
        T.pop()
        T.reverse()
    
    if len(T)==len(S):
        break

if S==T:
    print(1)
else:
    print(0)

• S->T가 아니라 T->S로 만들어질 수 있는지 검사한다.

 

 

---

# 회고

 

나에게 골드 문제는 이른 것 같다!

그리디 실버를...정복하고 다시 풀어봐야지