[이코테] 큰 수의 법칙

문제 풀면서 작성한 메모

풀이 과정

---

1. 문제를 정독하면서 메모한다. 주의해야 할 것은 ※으로 표시한다.

입력 첫째 줄에 배열의 크기 N, 주어진 수들을 더하는 횟수 M, 연속해서 초과하여 더해질 수 없는 횟수 K가 주어지고 둘째 줄에 배열에 해당하는 N개의 자연수가 주어진다. 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다는 것은 주의할 사항이므로 ※으로 따로 표시했다. 입력 조건도 메모했다. 그리고 문제에서 예시로 든 케이스를 하나하나 살펴보며 규칙을 찾으려 노력했다. 

2. 알고리즘을 떠올리고 적용하려고 노력한다.

이건 그리디 알고리즘 실전 문제이므로 이미 알고리즘은 알고 있었다. 그리디 알고리즘은 지금 당장 좋은 것만 선택하는 알고리즘이다. 지금 당장 좋은 것만 선택했을 때 나올 수 있는 경우의 수를 생각해보았다.

 

먼저, 가장 큰 수가 하나인 경우에는 K번을 초과하여 더할 수 없으므로 가장 큰 수를 K번 더하고 그다음 큰 수를 한번 더하는 과정이 M번에 도달할 때까지 반복된다. 이것이 예시로 든 [2, 4, 5, 4, 6] 케이스다.

 

가장 큰 수가 두 개 이상인 경우에는 같은 값이라도 서로 다른 것으로 간주하므로 가장 큰 수를 M번 더하면 된다. [3, 4, 3, 4, 3] 케이스가 이에 해당한다.

 

즉, 가장 큰 수가 하나인 경우에는 가장 큰 수와 그다음으로 큰 수만 저장하고, 가장 큰 수가 둘 이상인 경우에는 가장 큰 수만 저장하면 된다.

3. 필요한 변수에 대해서는 변수명을 작성한다.

N, M, K는 문제에서 주어졌으므로 변수명을 그대로 사용한다. 배열은 array, 가장 큰 수는 maxNum, 그다음으로 큰 수는 nextMaxNum으로 이름 지었다. 큰 수의 법칙에 따른 결과는 출력해야 하는 값이므로 answer라고 하겠다.

4. 바로 문제 풀지 말고 주석을 달며 의사 코드를 작성한다.

바로 코딩하지 않고 주석으로 의사 코드를 작성했다. 떠오르는 함수나 풀이 방법은 괄호 안에 작성했다. 특히 가장 큰 수가 몇 개 있는지 확인하는 부분은 최근 알고리즘 문제에서 사용했던 방법이 떠올라서 그걸 사용하기로 했다. 아래 링크를 첨부한다.

[PYTHON] 목록에서 최대 값의 모든 위치를 찾는 방법?

5. 의사 코드에 맞춰 구현한다.

# 입력받고 각 변수에 저장
N, M, K = map(int, input().split())
# print(N, M, K)

# 입력받고 배열 생성
array = []
array = list(map(int, input().split()))
# print(array)

# 가장 큰 수 확인
maxNum = max(array)
# print(maxNum)

# 가장 큰 수가 몇 개 있는지 확인
maxNumArray = [i for i, j in enumerate(array) if j == maxNum]
# print(maxNumArray)

# 1개면 다음으로 큰 수 확인
answer = 0
cnt = 0
if len(maxNumArray) == 1:
	array.remove(maxNum)
	nextMaxNum = max(array)
	# print(nextMaxNum)
	while cnt < M:
		for j in range(K):
			answer += maxNum
			cnt += 1
		answer += nextMaxNum
		cnt += 1
else:
	answer = maxNum * M
print(answer)

 

주석에 쓴 대로 코드를 작성했다. 추가적으로 maxNum에 해당하는 index를 담은 배열이 필요하여 maxNumArray를 선언했다. 가장 큰 수 다음으로 큰 수인 nextMaxNum을 구하기 위해 또 한 번 for문을 도는 것은 비효율적이라 생각해 아예 배열에서 가장 큰 수인 maxNum을 제거하고 max 함수로 nextMaxNum을 바로 구했다. 어차피 nextMaxNum은 maxNum이 한 개일 때만 구하면 되니 maxNum을 제거하면 maxNum 다음으로 큰 수는 max(array)가 될 것이다.

 

그런데 이렇게 다 작성하고 나니 꼭 가장 큰 수의 index를 저장할 필요는 없겠다는 생각이 들었다. 가장 큰 수가 어디에 있는지 중요한 게 아니라 가장 큰 수가 몇 개 있는지 확인하면 되는 것이다.

 

# 입력받고 각 변수에 저장
N, M, K = map(int, input().split())

# 입력받고 배열 생성
array = list(map(int, input().split()))

# 가장 큰 수 확인
maxNum = max(array)

# 가장 큰 수가 몇 개 있는지 확인
maxNumCnt = 0
for num in array:
    if num == maxNum:
        maxNumCnt += 1

# 1개면 다음으로 큰 수 확인
answer = 0
cnt = 0
if maxNumCnt == 1:
    array.remove(maxNum)
    nextMaxNum = max(array)
    # print(nextMaxNum)
    while cnt < M:
        for j in range(K):
            answer += maxNum
            cnt += 1
        answer += nextMaxNum
        cnt += 1
elif maxNumCnt >= 2:
    answer = maxNum * M

print(answer)

 

이제 maxNumArray는 필요 없다. 가장 큰 수가 몇 개 있는지 확인하기 위해 maxNumCnt를 새로 만들었다. array의 원소를 하나하나 돌며 maxNum과 같다면 maxNumCnt를 1씩 추가했다.

 

앞서 가장 큰 수가 1개인지(if) 혹은 1개가 아닌지(else)를 if else문으로 작성했는데, 정확히 말하면 1개인지(if), 2개 이상인지(elif)이므로 else를 elif문으로 바꿨다.

답안 예시

---

단순하게 푸는 답안 예시

# 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] # 두 번째로 큰 수

result = 0

while True:
	for i in range(k): # 가장 큰 수를 K번 더하기
    	if m == 0: # m이 0이라면 반복문 탈출
        	break
        result += first
        m -= 1 # 더할 때마다 1씩 빼기
    if m == 0: # m이 0이라면 반복문 탈출
    	break
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 때마다 1씩 빼기

print(result) # 최종 답안 출력

 

그리디는 정렬이랑 자주 짝을 이룬다는 점을 깜박했다! 정렬하고 나면 가장 큰 수와 그다음으로 큰 수의 위치를 알 수 있고 그다음으로 큰 수가 가장 큰 수와 같더라도 상관없다. 가장 큰 수가 1개인지 2개 이상인지 나눌 필요도 없이 1개일 때와 동일하게 적용해도 되는 것이다. 너무 저번에 배운 알고리즘에 꽂혀서 그걸 적용할 생각만 했던 것 같다. 그리디는 정렬과 자주 짝을 이룬다는 점을 잊지 말자.

 

그리고 나는 cnt를 새로 만들었는데 여기서는 이미 갖고 있는 변수 m을 이용했다. 이것도 생각 못했다..!

 

그런데 m이 0이라면 반복문을 탈출하는 부분이 두 번이나 반복되어 한 번으로 줄일 수 없는지 실험해보았으나 역시나 두 번이 필요했다. 간단하게 구현하긴 했지만 더 효율적으로 풀 수 있지 않나 아쉬움을 남기는 코드였다.

3-2.py 답안 예시

# 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) # 최종 답안 출력

 

이건 생각지도 못한 풀이였다. 문제 풀이가 어느 정도 규칙이 있다고는 생각했는데 함수화할 생각은 못했다. 그러고 보니 가장 큰 수가 K만큼 반복되고 나면 두 번째로 큰 수를 더하는 과정이 반복된다. 이 반복되는 수열의 길이는 (K+1)이고, M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 물론 M이 (K+1)로 나누어 떨어지지 않을 수 있다. 이 경우 나머지만큼 가장 큰 수를 더해주면 된다. 즉, 이를 식으로 나타내면 다음과 같다.

 

큰 수의 법칙에 따른 결과 = (가장 큰 수 * K + 두 번째로 큰 수) * (M // (K+1)) + 가장 큰 수 * (M % (K+1))

 

3-2.py 답안은 가장 큰 수가 더해지는 횟수를 count로 계산하고 (m-count)만큼 두 번째로 큰 수를 더하는 방식으로 최종 답안을 출력했다. 하지만 count 없이도 위의 구한 공식대로 바로 구할 수 있다 생각하여 3-2.py를 고쳐보았다.

 

# 입력받고 각 변수에 저장
N, M, K = map(int, input().split())

# 입력받고 배열 생성
array = list(map(int, input().split()))

array.sort()
maxNum = array[N-1] # 가장 큰 수 확인
nextMaxNum = array[N-2] # 두 번째로 큰 수 확인

answer = (maxNum * K + nextMaxNum) * (M // (K+1)) + maxNum * (M % (K+1))

print(answer)

 

결과도 원하는 대로 나온다. 좀 더 효율적으로 구현한 것 같아 만족스러웠다. 여기서 더 들어가면 아래 코드와 같이 maxNum이 nextMaxNum과 같다면 maxNum * M으로 바로 answer를 구할 수도 있다.

 

# 입력받고 각 변수에 저장
N, M, K = map(int, input().split())

# 입력받고 배열 생성
array = list(map(int, input().split()))

array.sort()
maxNum = array[N-1] # 가장 큰 수 확인
nextMaxNum = array[N-2] # 두 번째로 큰 수 확인

if maxNum != nextMaxNum:
  answer = (maxNum * K + nextMaxNum) * (M // (K+1)) + maxNum * (M % (K+1))
else:
  answer = maxNum * M

print(answer)

코드 수행 시간 비교 (왼) if문 O, (오) if문 X

 

if문이 있는 것이 더 효율적일 줄 알았는데, timeit 모듈로 코드 수행 시간(초)을 측정해보니 if문이 없는 것이 더 빨랐다. 따라서 if문이 없는 코드를 최종 코드로 결정! 코드 수행 시간 측정은 아래 링크를 참고했다.

코드 수행 시간을 어떻게 측정하나요?

개념 정리

---

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

-> 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

그리디 알고리즘의 경우 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해 준다. 이는 정렬 알고리즘을 사용했을 때 만족시킬 수 있어 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 책에 나온 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 따라서 처음에 문제를 만났을 때는 항상 최적의 해를 보장할 수 있을 때까지 이것저것 다양한 아이디어를 고려해야 한다.

 

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 이후 배우게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보는 것도 한 방법이다.

코드

---

GitHub - leeejihyun/algorithm: 알고리즘 문제 풀이

출처

---

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2021), p86-95