[codility] L16 Greedy : TieRopes (python)

 

https://app.codility.com/programmers/lessons/16-greedy_algorithms/

16. Greedy algorithms lesson - Learn to Code - Codility

 

 

There are N ropes numbered from 0 to N − 1, whose lengths are given in an array A, lying on the floor in a line. For each I (0 ≤ I < N), the length of rope I on the line is A[I].

 

# 0~ N-1까지의 번호가 매겨진 N개의 rope가 있다. 

# A라는 배열엔 N개 로프의 길이가 있다.   >> 줄 i번쨰 로프의 길이는 A[i]

 

We say that two ropes I and I + 1 are adjacent.

# i와 i+1번째 로프는 인접해 있다. 

 

Two adjacent ropes can be tied together with a knot, and the length of the tied rope is the sum of lengths of both ropes.

# 두개의 인접한 로프는 매듭으로 묶을 수 있고 그 길이는 두 로프의 합이다.

 

The resulting new rope can then be tied again.

# 묶인 로프는 다시 묶일 수 있다. 

 

For a given integer K, the goal is to tie the ropes in such a way that the number of ropes whose length is greater than or equal to K is maximal.

# K가 주어졌을 때,

로프를 묶어 k보다 크거나 같은 로프의 개수가 최대가 되도록 하는것.

 

 

<예시> k = 4, A = [1,2,3,4,1,1,3] 일때

4보다 크거나 같도록 묶는 경우는...

 

For example, consider K = 4 and array A such that:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 1 A[5] = 1 A[6] = 3

The ropes are shown in the figure below.

We can tie:

• rope 1 with rope 2 to produce a rope of length A[1] + A[2] = 5;
• rope 4 with rope 5 with rope 6 to produce a rope of length A[4] + A[5] + A[6] = 5.

# 1번 로프 + 2번 로프 >> 2+3 = 5

# 4번 로프 + 5번 로프 + 6번 로프 = 1 + 1 + 3 =5 

<솔직히 예시 4보다 크거나 같은걸로 두는데 왜 이렇게 두개 둔건지 모르겠음>

 

After that, there will be three ropes whose lengths are greater than or equal to K = 4. It is not possible to produce four such ropes.

# 길이가 K(4)보다 크거나 같은 로프는 3개가 된다. 4개를 만드는것은 불가능

 

 

 

Write a function:

def solution(K, A)

that, given an integer K and a non-empty array A of N integers, returns the maximum number of ropes of length greater than or equal to K that can be created.

For example, given K = 4 and array A such that:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 1 A[5] = 1 A[6] = 3

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• K is an integer within the range [1..1,000,000,000];
• each element of array A is an integer within the range [1..1,000,000,000].

N : [1..100,000]의 정수
K : [1..1,000,000,000]의 정수
A의 각 요소 : [1..1,000,000,000]의 정수

 

 

 

<알고리즘 사고>

K보다 크거나 같은 로프의 최대 개수를 반환하는 것이기 때문에 무조건 K를 맞출 필요는 없고

인접한 로프끼리 묶일 수 있기 때문에 

0번째 로프부터 시작, 끝까지반복 ( for i in A )

 

sum =0으로 초기화 후

각 로프의 길이를 더해주다가 K보다 값이 커질 때 count +=1 해주도록 했다. 

 

 

(100%)

def solution(K, A):
    count = 0
    sum = 0
    for i in A:
        sum += i
        if sum >= K:
            count+=1
            sum = 0

    return count

 

 

영어문제는 해석하는게 일인데 codility 는 특히 더 고려해야 할게 많은 느낌이다. 

 

효율적인 알고리즘인지에 따라 점수가 갈려서 ㅠㅠ

1) 문제가 쉬운데도 100점 못맞음

2) 테케 맞아도 점수 30점대 나오는거 보다보면 아 이래서 내가 코테 합격을 그동안 못했구나 싶음 ㅋㅋㅋ

 

 

 

코딜리티를 통해 아직 부족하고 앞으로도 꾸준하게 열심히 해야겠다는 생각을 했다.