[이것이 코딩테스트다] 그리디 - 큰 수의 법칙 문제풀이

문제

다양한 수로 이루어진 배열이 있을때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

 

list = [2, 4, 5, 4, 6], M = 8, K = 3

이 경우 특정한 인덱스의 수가 연속해서 세번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 6 = 46이 된다.

 

 

 

 

나의 코드 

# 가장 큰 수를 k번 반복
# 두번째로 작은 수를 k번 반복 후 넣고 또다시 가장 큰수 반복
# 위를 실행하며 M개 미만인지 체크해야한다.

test = [2, 4, 5, 4, 6]

m = 8  # 개수 제한
k = 3  # 반복 개수 제한

# 가장 큰 수
max_value = max(test)

# 가장 큰수 제거
test.pop(test.index(max_value))
print(test)

# 가장 큰수가 제거된 리스트에서 가장 큰 수 (처음 리스트의 두번째 큰 수)
max_second = max(test)

result = 0

# k 를 담은 변수 선언
copy_k = k

for i, v in enumerate(range(m)):
    # 가장큰 수를 k번 더했을때 두번째로 가장 큰 수를 더하고 copy_k 를 다시 k로 셋팅
    if copy_k == 0:
        result += max_second
        copy_k = k
    else:
        # 가장 큰 수를 더한다.
        result += max_value
        copy_k = copy_k - 1


print(result)

 

가장 먼저 가장 큰 수를 구하여 변수에 저장한다. 그리고 리스트에 가장 큰 수를 제거한 후 다시 리스트에서 가장 큰 수를 찾는다. (처음 리스트에서 두번째로 큰 수를 찾은 것이다.) copy_k라는 변수를 생성하여 K값을 저장한다. 그리고 반복문을 실행하여 가장 큰 수를 copy-k만큼 더한다. 더한 이후에는 copy_k- 1을 실행하여 계속 반복문을 실행하며 K가 0일 경우에 두번째 큰 수를 더하고 다시 copy_k 변수에 K를 할당해준다.

 

 

 

정답코드

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())

# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort()  # 입력 받은 수 정렬

first = data[n - 1]  # 마지막 원소 = 제일 큰 수
second = data[n - 2]  # 두번째로 큰 수 = 마지막에서 두번재 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)


result = 0
result += count * first  # 가장 큰 수 더하기
result += (m - count) * second  # 두번째로 큰 수 더하기

print(result)

출처: github.com/ndb796/python-for-coding-test/blob/master/

 

 

 

 

문제풀이

(1) 설명

data.sort()  # 입력 받은 수 정렬

 

해당 정답 코드에서는 원소의 위치로 가장 큰수와 두번째로 큰 수를 찾고있다. 따라서 리스트의 정렬이 필요하다.

 

 

(2) 설명

first = data[n - 1]  # 마지막 원소 = 제일 큰 수
second = data[n - 2]  # 두번째로 큰 수 = 마지막에서 두번재 수

 

정렬된 리스트에서 제일 큰수와 두번째로 큰 수를 각 변수에 담았다.

 

 

(3) 설명

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)

 

가장 큰 수가 더해지는 횟수를 계산하여 count에 담았다. 위 예시에서 list = [2, 4, 5, 4, 6], M = 8, K = 3 일 경우에 가장 큰수인 6이 총 6번 더해졌고, 두번째로 큰 수인 5가 2번 더해졌다. 가장 큰수가 총 더해지는 횟수를 구하면 M - 횟수를 하여 두번째 수가 더해지는 횟수를 구할 수 있다. 따라서 정답 코드에서는 위 식을 활용하여 총 더해지는 횟수를 구한 로직이다.

 

아래에서는 가장 큰 수를 count만큼 더하고, 두번째로 큰 수를 (m - count)만큼 더하게된다. 총 덧셈을 실행할 횟수는 M번이고, 가장 큰 수를 연속적으로 더할 수 있는 횟수는 K번이다. 

 

 

(4) 설명

result = 0
result += count * first  # 가장 큰 수 더하기

 

출력값을 result에 담을 것이다.

우선, 가장 큰 수를 count 만큼 곱해서 저장한다. (가장 큰 수를 count번 더한 것이다.)

 

 

(5) 설명

result += (m - count) * second  # 두번째로 큰 수 더하기

 

(m - count)로 위에서 가장 큰 수를 더한 횟수를 제외한 나머지 횟수만큼 두번째로 큰 수를 더한다.