[이코테] 그리디_큰 수의 법칙(자바스크립트)

이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고

---

문제

---

정답 코드

이전 나의 답안

나의 답안

답안 1

답안 2

---

문제 풀이

 문제를 풀 때 가장 먼저 해야 하는 작업은 입력 받은 숫자들을 정렬하는 것이다. 왜냐하면 이 문제에서는 첫 번째로 큰 수와 두 번째로 큰 수만이 사용되기 때문이다.

 나의 경우 만약 첫 번째로 큰 수와 두 번째로 큰 수가 같다면 첫 번째로 큰 수만 결괏값에 다 더했다. 이 경우 첫 번째로 큰 수와 두 번째로 큰 수를 번갈아가며 더한 경우와 첫 번째로 큰 수만 더한 경우의 결괏값이 같기 때문이다. 두 값이 같지 않고 cnt가 k와 같지 않다면 첫 번째 큰 수 결괏값에 더하고 cnt 증가, cnt와 k가 같아지면 두 번째로 큰 수를 결괏값에 더한 뒤 cnt를 0으로 초기화했다.

 답안 1의 경우 이중 반복문을 돌면서 결괏값을 구하는 풀이이다. 반복문을 도는 동안 가장 큰 수를 k번 더하고, 그 다음 큰 수는 한 번만 더한다. 각 작업이 수행될 때마다 m을 1씩 감소시킨다. 작업을 수행하다 m이 0이 될 때 반복문을 빠져나오고 결괏값을 반환한다.

 하지만 위와 같이 반복문을 활용했을 때 m의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받는다. 따라서 진정한 답을 얻으려면 답안 2처럼 수학적 아이디어를 활용해 문제를 풀어야 한다.

 다음과 같은 입력이 주어졌을 때 계산 과정을 살펴보자.

const [n, m, k] = [5, 8, 3];
const data = [2, 4, 5, 4, 6];

// 가장 큰 수: 6
// 두 번째로 큰 수: 5

 위와 같은 입력이 주어졌을 때 가장 큰 합은 46을 구하려면 다음과 같이 더해야 한다.

 특정한 수열 형태로 반복해서 더해지는 특징을 볼 수 있다. 위 예시에서 반복되는 수열의 길이는 4인데 이는 (k + 1)이다. 따라서 m을 (k + 1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 여기에 k를 곱하면 가장 큰 수가 등장하는 횟수이다. k는 가장 큰 수를 연속해서 더하는 횟수이기 때문이다.

 이때 m이 (k + 1)로 나눠떨어지지 않는 경우도 고려해야 한다. 이 때는 m을 (k + 1)로 나눈 나머지만큼 큰 수가 더 등장한다. 이를 정리해 '가장 큰 수가 더해지는 횟수'를 코드로 나타내면 다음과 같다.

parseInt(m / (k + 1)) * k + m % (k + 1)

 위의 식을 활용하여 가장 큰 수가 더해지는 횟수를 구해, 결괏값에 가장 큰 수의 합을 더한 다음, 두 번째로 큰 수의 합을 더하면 정답이 된다.