[이것이 취업을 위한 코딩 테스트다 with 파이썬] 큰 수의 법칙

종강하자마자 코딩테스트 공부를 해오고 있는데, 매주 알고리즘별로 공부를 해오고 있다 !!!!

근데 책 하나를 한 번 보는 것도 나쁘지 않을거 같아서 코테에서 많이 쓰는 알고리즘을 한번 전반적으로 공부를 하는 중이다 ! 😆

 

우선 처음에 Greedy에 관해 연습을 했다.

 

해당 책의 그리디 문제에서 내 풀이와, 주어진 풀이를 보고 다시 풀어본 것을 비교해보면 뭔가 머리를 띵 맞은 기분...

나의 경우는 while문과 for 때문에 시간 복잡도가 컸다.... 책으로 한번 공부해보기 좋았던 것 같다... 굿굿

 

# 첫 풀이
#m번 더하여 가장 큰 수를 만드는 법칙 ,연속해서 k번을 초과하면 안된다.
n,m,k = map(int,input().split())

num = list(map(int,input().split()))
num.sort()

maxNum=num[n-1]
nextNum=num[n-2]
sumList=list()

while len(sumList)!=m:
    for j in range(k):
        sumList.append(maxNum)
    sumList.append(nextNum)
print(sum(sumList))

나의 첫 풀이다. 

while 문의 조건을 sumList의 길이로 잡아놓고 풀었다.

while문안에 for문을 또 쓰는 것을 볼 수 있다.

 

# 두 번째 풀이

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

num = list(map(int,input().split()))
num.sort()

maxNum=num[n-1]
nextNum=num[n-2]

# *** 가장 큰 수 가 더해지는 횟수 구하기 ***

# (k+1)의 k는 가장 큰수의 개수 , 1은 그 다음으로 큰수 개수
# 이를 m에 나누면 해당 수열이 반복되는 횟수
# 거기에 k를 곱하면 가장 큰수가 나오는 횟수
count = int(m/(k+1))*k

# 그리고 해당 수열만큼 나누어 떨어지지 않는 경우도 있으니
count += m % (k+1)

# *** 그다음 큰 수가 더해지는 횟수 구하기 ***

# m번 더해야하는데 위에서 구한 가장 큰 수가 더해지는 횟수를 빼면 된다
nextCount = m-count

# 결과 값
result = 0
result += count * maxNum
result += nextCount * nextNum

print(result)

책의 답안을 이해해보고 다시 풀어본 코드이다.

반복 문을 찾아 볼 수 없다.

문제를 통해 숨어진 식을 찾아내야 했다.

훨씨 간단했다...굿굿