📚 1. 그리디 정리

📖 A. 그리디

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
• '현재 상황에서 특정한 기준에 따라 가장 좋아 보이는 것만을 선택' 해서 최적의 해를 구해야한다.
• 코딩 테스트에서는 대부분 '최적의 해'를 찾는 문제가 출제되기 때문에 그리디 알고리즘의 정당성을 고민하면서 문제 해결 방안을 떠올려야 한다.
• 거스름돈 문제와 같이 자연수 N이 1이 될때까지 최소 몇 번을 수행해야 하는지 계산
• 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘은 모두 그리디 알고리즘이다.

📚 2. 문제

📖 Q 1 모험가 길드

n = int(input())
list_data = []

list_data = list(map(int,input().split()))

list_data.sort()
last_data = list_data[n-1]
total_cnt = 0

for idx in range(1,last_data+1):
    if list_data.count(idx) >= idx:
        total_cnt += 1

print(total_cnt)

📖 Q 2 곱하기 혹은 더하기

s = input()

list_data = list(s)
check_cal = False
result = 1

list_data.sort()
print(list_data)
for idx in range(len(list_data)):
    if list_data[idx] == '0':
        continue

    if check_cal == False and list_data[idx] == '1':
        result += 1
    else:
        check_cal = True
        result *= int(list_data[idx])

print(result)

📖 Q 3 문자열 뒤집기

s = input()

before = 0
cnt_0 = 0
cnt_1 = 0

for idx in range(1, len(s)):
    if s[before] != s[idx] and s[before] == '0':
        cnt_0 += 1
        before = idx
    elif s[before] != s[idx] and s[before] == '1':
        cnt_1 += 1
        before = idx

if s[len(s)-1] == '0':
    cnt_0 += 1
else:
    cnt_1 += 1


if cnt_0 > cnt_1 :
    print(cnt_1)
else:
    print(cnt_0)

📖 4. 만들 수 없는 금액

n = int(input())
data = list(map(int,input().split()))
data.sort()

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x

# 만들 수 없는 금액을 찾았을 때 반복 종료
print(target)

📖 5. 볼링공 고르기

# 무게가 1인 볼링공 : 1개
# 무게가 2인 볼링공 : 2개
# 무게가 3인 볼링공 : 2개


# A가 무게가 1인 공을 선택할 때의 경우의 수는
# 1 * 4 (2개 2개)
# A가 무게가 2인 공을 선택할 때의 경우의 수는
# 2 * 2 (2개)
# A가 무게가 2인 공을 선택할 때의 경우의 수는
# 2 * 0 (0개)


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

# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11

for x in datalist:
    array[x] += 1

result = 0
for i in range(1, m + 1):
    n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i] * n # B가 선택하는 경우의 수와 곱하기

print(result)

📖 6. 무지의 먹방 라이브

import heapq


def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    print(food_times)
    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i + 1))

    sum_value = 0  # 먹기 위해 사용한 시간
    previous = 0  # 직전에 다먹은 음식 시간
    length = len(food_times)  # 남은 음식의 개수
    print(q)
    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1  # 다먹은 음식 제외
        previous = now  # 이전 음식 시간 재설정

    print(q)
    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1])  # 음식의 번호 기준으로 정렬
    print(result)
    return result[(k - sum_value) % length][1]


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