greedy-(2)

1. 볼링공 고르기 [2019 SW 마에스트로 입학 테스트]

#볼링공 고르기 => 두사람이 무게가 다른 볼링공을 고르는 경우의 수를 출력하는 문제

n,m = map(int,input().split()) 
#n개의 공이 m까지의 숫자로 구성됨

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

count=0

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

print(count)

2. 무지의 먹방 라이브[2019 카카오 신입 공채]

 

 

효율성 0점 + 시간초과로 정확성도 1개 틀린 결과

 

#무지의 먹방 라이브

eat = list(map(int,input().split()))
k = int(input())

time =0
i=0
cnt=0
while True:
    if time==k:
        if eat[i]>0:
            print(i+1)
            break
    if eat[i]>0:
        eat[i]=eat[i]-1
        time+=1
    if i==len(eat)-1:
       i=0
    else:
        i+=1
    count=0
    for j in range(0,len(eat)):
        if eat[j]==0:
            count+=1
    if count==len(eat):
        print("-1")
        break
#https://programmers.co.kr/learn/courses/30/lessons/42891 에 참고

=> 무지의 먹방 라이브 문제를 위의 알고리즘에서 위의 사이트의 기본 소스코드에 맞게 변경한결과 효율성이 0점이 나왔고 아마도 for문을 돌려서 -1을 체크한 것이 원인인 것으로 보여지고 다시 생각해봐야할 문제.

 

=> 효율성 문제는 현재 그리디를 연습하기 위해서 다른 알고리즘을 사용하지 않았기때문에 발생한 것으로 보임.

=> 정확성에서 1문제가 틀린 부분은 시간초과가 나지 않게 코드를 줄여봄.

def solution(food_times, k):
    time =0
    i=0
    if sum(food_times)<=k:
        return -1
    while True:
        if time==k:
            if food_times[i%len(food_times)]>0:
                return i%len(food_times)+1
        if food_times[i%len(food_times)]>0:
            food_times[i%len(food_times)]=food_times[i%len(food_times)]-1
            time+=1
        i+=1
        c = food_times.count(0)
        if c==len(food_times):
            return -1

위의 코드를 https://programmers.co.kr/learn/courses/30/lessons/42891#에 제출한 결과

정확도는 만점으로 고칠 수 있었음

해결방법 =>

- if문을 추가해서 -1 처리를 할 때 시간을 단축시켰고 while문에서는 i%len(food_time)를 활용해 나머지를 활용해 i를 증가시키며 마지막 값이 될때 0으로 돌아오게 하는 코드를 따로 작성할 필요를 없앰.

- 또한 for문으로 food_times에서의 0을 카운트할 때 .count()함수에 인자로 0을 넣어 작성해서 시간을 줄임

 

3. 만들 수 없는 금액[k대회 기출] => 다시하기