이코테 - 그리디 기출

Q-01 모험가 길드

나의 코드)

n = int(input())

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

count = 0
result = 0

for i in array:
  count += 1
  if count == i:
    result += 1
    count = 0

print(result)

Q-02

array = list(map(int,input()))

result = 1

array.sort()

# 0과 1의 마지막 인덱스
index = -1
for i in range(len(array)):
  if array[i] <= 1:
    index = i

first = sum(array[0:index+1])
    
# 1 초과 값들만
array = array[index+1:]
print(array)
result = 1

# 1 이하
if first <= 1:
  array[-1] += first
  for i in array:
    result *= i
  
  #2 이상
else:
  array.append(first)
  for i in array:
    result *= i

print(result)
    

comment) 난 존나 바보다. 뭘그리 어렵게 생각할까

Q-03 문자열 뒤집기

array = list(map(int,input()))


# 0과 1의 뭉티기 횟수
zero = 0
one = 0

# 인덱스 0값 에 따른 뭉티기 추가
first = array[0]
if first == 1:
  one += 1
else:
  zero += 1

#변화시 뭉티기 추가

for i in range(len(array)-1):

  if array[i] == 0 and array[i+1] == 1:
    one += 1
  if array[i] == 1 and array[i+1] == 0:
    zero += 1  


# 비교후 산출

if zero >= one:
  print(one)

else:
  print(zero)

Q-05 볼링공 고르기

나의 코드)

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

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

count = 0

for i in range(n):
  for j in range(i+1,n):
    if array[i] != array[j]:
      count += 1

print(count)

책 코드)

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

array = [0] * 11

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

result = 0
for i in range(1,m+1):
  n -= array[i]
  result += n * array[i]

print(result)

시간 복잡도가 훨씩 적다

Q6 무지의 먹방 라이브

import heapq

def solution(food_times,k):
  if sum(food_times) <= k:
    return -1

  q = []
  for i in range(len(food_times)):
    heapq.heappush(q,(food_times[i],i+1))

  sum_value = 0
  previous_value = 0
  length = len(food_times)

  while sum_value + ((q[0][0]-previous_value)*length) <= k:
    now = heapq.heappush(q)[0]
    sum_value = now * length
    previous_value = now
    length -= 1

  result = sorted(q,key = lambda x: x[1])
  return result[(k-sum_value)%length][0]

comment) 어렵다. 우선순위 큐로 푸는 문제일 줄은 상상도 못했다. 문제를 계속 풀어보며 유형을 익혀야 겠다.