[이코테 파이썬] #01. 그리디 알고리즘

>>강의

 

#1. 모험가 길드

 

>내가 푼 풀이

group=[]
cnt=0
n= int(input())
scared= list(map(int, input().split()))
scared.sort()

for i in scared:
  group.append(i)
  if len(group)==max(group):
    cnt+=1
    group=[]

print(cnt)

 

> 답안 소스코드

# 답안 소스코드

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

result=0 # 총 그룹의 수
count=0 #현재 그룹에 포함된 모함가의 수

for i in data: # 공포도를 낮은 것부터 확인
  count+=1 # 현재 그룹에 해당 모험가 포함시키기
  if count>=i: #현재 그룹에 포함된 모험가의 수가 현재 공포도 이상이라면 그룹 결성
    result+=1 # 총 그룹 수 증가
    count=0 # 현재 그룹에 포함된 모함가의 수 초기화

print(result) # 총 그룹의 수 출력

 

 

02. 곱하기 혹은 더하기

 

>>내가 푼 풀이

#02 곱하기 혹은 더하기

#1이하의 수는 덧셈이 더 유리하지만 2이상부터는 곱셈이 유리함

result=0

k=input()

for i in k:
  i= int(i)
  if i <2 or result<2:
    result+=i
  else:
    result*=i

print(result)

 

>> 답안 소스코드

data= input()

#첫째 문자를 숫자로 변경하여 대입
result= int(data[0])

for i in range(1, len(data)):
  #두 수 중 하나라도 0 혹은 1인 경우, 곱하기보다는 더하기 수행
  num= int(data[i])
  if num<=1 or result<=1:
    result+=num
  else:
    result*=num

print(result)

 

 

03. 문자열 뒤집기

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

1439번: 뒤집기

 

>>내 풀이

#03. 문자열 뒤집기

data= input()
flag= int(data[0])
cnt0=0
cnt1=0

if flag==0:
  cnt0+=1
else:
  cnt1+=1

for i in data:
  i=int(i)
  if i==1 and flag==0:
    cnt1+=1
    flag=1
  elif i==0 and flag==1:
    cnt0+=1
    flag=0

print(min(cnt0, cnt1))

 

>>답안 소스코드

#03. 답안 소스코드

#전부 0으로 바꾸는 경우나 전부 1로 바꾸는 경우 중 더 적은 횟수

data= input()

count0=0 # 전부 0으로 바꾸는 경우
count1=0 # 전부 1로 바꾸는 경우

#첫번째 원소에 대해 처리
if data[0]=="1":
  count0+=1
else:
  count1+=1

#두번째 원소부터 모든 원소를 확인
for i in range(len(data)-1):
  if data[i]!= data[i+1]:
    #다음 수에서 1로 바뀌는 경우
    if data[i+1]=="1":
      count0+=1
    #다음 수에서 0으로 바뀌는 경우
    else:
      count1+=1

print(count0, count1)

 

 

>>04. 만들 수 없는 금액

 

>나의 풀이 : 생성가능한 전체 금액을 잡아서 풀이 => 시간/공간 복잡도가 너무 많음

#전체 경우의 수?
from itertools import combinations

money=set()
n= int(input())
coin= list(map(int, input().split()))

for i in range(1, n+1):
  coin_case= [sum(i) for i  in list(combinations(coin, i))]
  for j in coin_case:
    money.add(j)

result=1
flag=True
while(flag):
  if result not in money:
    flag=False
    break
  
  result+=1

print(result)

 

 

> 답안 소스코드

target-1까지 모든 금액을 만들 수 있다고 가정한 후, 작은 순서대로 확인하며 target을 만들 수 있는지 확인

 

 

ex) 1 2 3 8이 있다면

1) 금액 1을 만들 수 있는지 확인하기 위해 target=1로 잡음

2) target=1을 만들 수 있는지 확인, 우리에겐 화폐1이 있으므로 1을 만들 수 있음 target=1+1=2로 업데이트

3) target=2를 만족하는지 확인, 화폐단위 2가 있음 => target=2+2=4로 업데이트

4) target=4를 만족하는지 확인 화폐단위 3이 있음 => target= 4+3=7로 업데이트

5) target=7을 만족하는지 확인, 화폐단위 8이 있음 => 불만족

==> 1-6까지 생성이 가능한데, 8이면 1+8=9부터 가능

=> 7이 정답이 됨

n= int(input())

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

for i in data:
  if i>target:
    break
  target+=i

#만들 수 없는 금액 출력
print(target)

 

>> 5. 볼링공 고르기

 

>>나의 풀이

#5. 볼링공 고르기

#볼링공 개수와 최대 볼링공 무게
n,m= map(int, input().split())
balls= list(map(int, input().split()))
weight=[0]*(m+1)

#하나씩 카운트
for i in balls:
  weight[i]+=1

result=0

#무게 조합에 따라 경우의 수 더해주기
for i in range(1, m):
  if weight[i]==0:
    continue
  for j in range(i+1, m+1):
    result+=weight[i]*weight[j]
  
print(result)

 

>>답안 소스코드

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

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

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

for x in data:
  #각 무게에 해당하는 볼링공의 개수 카운트
  array[x]+=1

result=0
#1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m+1):
  n-=array[i] #무게가 i인 볼링공의 개수 제외
  result+=array[i]*n

print(result)

 

 

>>06. 무지의 먹방 라이브

https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3

프로그래머스

 

>>내가 제출한 답안 : 효율성 케이스를 통과하지 못함

from collections import deque
food_times= (list(map(int, input().split())))
q=deque([(time, idx+1) for idx, time in enumerate(food_times)])
k= int(input())


while(k>=len(q)):
  k-=len(q)
  q= deque([(time-1, idx) for time, idx in q if time !=1])
  if len(q)==0:
    break


for _ in range(k):
  if len(q)==0:
    print(-1)
    break

  time, idx= q.popleft()
  time-=1
  if time>0:
    q.append((time, idx))

print(q[0][1])

 

>>답안 소스코드

from collections import deque
import heapq

def solution(food_times, k):
    if k>=sum(food_times):
        return -1
    
    #시간, +순서
    q=[]
    for idx, i in enumerate(food_times):
        heapq.heappush(q, (i, idx+1))
    
    sum_value=0 #먹기 위해 사용한 시간
    previous= 0 #직전에 다먹은 음식 시간
    length= len(food_times) #남은 음식의 개수
    
    while (sum_value+(q[0][0]-previous)*length) <=k:
        now= heapq.heappop(q)[0]
        sum_value+=(now-previous) *length
        length-=1
        previous=now
    
    #남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result= sorted(q, key= lambda x: x[1])
    return result[(k-sum_value)%length][1]