[python3] 이것이 취업을 위한 코딩 테스트다 - 큰 수의 법칙 (ch.3 그리디)

내돈내산

참고) 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 기반으로 작성된 문제와 코드입니다. 
따라서 문제는 자세하게 적지 않고, 간단한 설명과 제 코드만 올리겠습니다.

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

 

실전 문제 (1) 큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰수를 만들어 보아라.
(단, K번을 초과해서 더할 수 없다)

입력은 N M K 
N: 배열의 크기
M: 숫자가 더해지는 횟수 
K: 주어지는 수 (K는 항상 M보다 작다)

<입력 예시>

5  8  4
2  4  5  4  6

<출력 예시>
46

 

<문제 풀이>

1. 배열에서 가장 큰 수를 찾아서 K를 곱한다 (K번 더해주는 것 이므로)
2. 그럼 더한 횟수 count는 k가 된다. 
3. 두번째로 큰 수를 1번 더해준다.
4. 그럼 더한 횟수 count는 k + 1이 된다. 
5. 현재의 count가 M보다 작으면, 과정을 반복해서 더해주고, 같으면 반복문을 탈출한다.

<내가 푼 코드>

나는 sort()를 활용하여 오름차순으로 정리를 해주었다. 

그리고 큰 수와 두 번째로 큰 수를 더해가는 과정이기에, 필요한 숫자가 딱 두개 인 만큼, num1과 num2에 저장해둔 채로 활용했다.

def solution(N, M, K):
    N.sort()
    total = 0
    num1 = N.pop()
    num2 = N.pop()
    max_k = 1
    for i in range(0, M):
        if max_k <= K:
            total += num1
            max_k += 1
        else: # K가 넘어가면
            max_k = 1 #max_k를 초기화 시켜줌
            total += num2
    return total

출력)

N = [4,3,4,6,9,10]  #차원
M = 5  #더해지는 횟수
K = 2  #연속 최대 몇번?

solution(N, M, K)

 

<예시 코드와 비교>

• pop()을 활용하여 정렬된 값들 중 맨 오른쪽에 있는 값을 꺼냈다. pop말고 다른 방법으로는 list[N-1], list[N-2] 처럼 인덱스로 찾는 방법도 있다. (N차원이니까, N-1이 가장 끝에 있는 수겠지?
• 나는 max_k라는 변수를 두고 +1 씩 더해가면서  K의 값을 비교해가는 반복문을 사용했다. (반복문은 총 M번 돌아가게 만듦)
• 반면에 예시 코드는, while == True 문을 활용하여 무한대로 돌게 만들고, 계산을 한번씩 돌때마다 M 에서 -1 씩 뺴주었다. 그리고 M ==0 이 되는 순간에 break 하면서 while문을 탈출했다. 
• 이번 코드는 어떤게 더 낫다 라고 볼만한 게 없다. 어쨋든, 반복문을 활용한것도 같고, -1씩 하냐, +1씩하냐 시간 복잡도도 거기서 거기일 것 같다. (시간 복잡도 아직 구하는 법을 잘 모른다 ㅠㅠ 공부해야한다)