큰 수의 법칙

이코테 그리디 알고리즘 문제 중 하나인 큰 수의 법칙 문제이다.

자연수가 주어졌을 때, M번 더하여 가장 큰 수를 만드는 문제인데 연속해서 K번까지만 더할 수 있다는 조건이 있다.

가장 큰 수를 만들기 위해서는 첫 번째로 큰 수를 M번 더하면 되는데 연속해서 K번까지만 더할 수 있다는 조건이 있어서 두 번째로 큰 수를 1번 더하고 다시 첫 번째로 큰 수를 반복해서 더하면 된다.

먼저, 입력받은 자연수로 배열을 생성하여 오름차순 정렬한 후 첫 번째로 큰 수와 두 번째로 큰 수만 필요로 하기 때문에 변수에 저장하였다.
두 번째로, 더할 때마다 횟수를 증가시킬 cnt 변수와 최종 결과값을 저장할 result 변수를 초기화하였고 반복문을 돌면서 m을 1씩 감소시켰다.
이 때, cnt가 k와 같아지면 두 번째로 큰 수를 더해주었고 각 반복마다 m을 1씩 감소시켜 0이 되면 반복문을 빠져나오게 구현하였다.

풀이 시간을 30분으로 정해놓고 풀었다. 여러 가지 풀이 방법이 있을 수 있다고 생각했고 일단은 답을 구하는 데에 초점을 맞춰서 풀었다. 이후 다양한 풀이를 보며 이전 코드를 개선해보았다.

첫 번째 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 큰수의법칙 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 수의 개수
        int m = Integer.parseInt(st.nextToken()); // 더하는 횟수
        int k = Integer.parseInt(st.nextToken()); // 연속해서 더할 수 있는 횟수
        int[] numArr = new int[n]; // n개의 자연수
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numArr.length; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numArr); // 오름차순 정렬
        int firstMax = numArr[numArr.length - 1]; // 첫 번째로 큰 수
        int secondMax = numArr[numArr.length - 2]; // 두 번쨰로 큰 수
        int cnt = 0;
        int result = 0;
        while (true) {
            result += firstMax; // 첫 번째로 큰 수 더하기
            cnt++; // 더하는 횟수 카운트
            m--; // 더할 때마다 m 감소
            if (cnt == k) {
                result += secondMax; // 두 번째로 큰 수는 한 번만 더해도 됨
                cnt = 0;
                m--;
            }
            if (m == 0) {
                break; // m번만큼 더하면 종료
            }
        }
        System.out.println(result);
    }
}

분명 더 깔끔한 코드가 있을 것 같다는 생각이 들었다.

두 번째 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 큰수의법칙 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 수의 개수
        int m = Integer.parseInt(st.nextToken()); // 더하는 횟수
        int k = Integer.parseInt(st.nextToken()); // 연속해서 더할 수 있는 횟수
        int[] numArr = new int[n]; // n개의 자연수
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numArr.length; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numArr); // 오름차순 정렬
        int firstMax = numArr[numArr.length - 1]; // 첫 번째로 큰 수
        int secondMax = numArr[numArr.length - 2]; // 두 번쨰로 큰 수
        int cnt = 0;
        int result = 0;
        for (int i = 0; i < m; i++) {
            cnt++; // 더하는 횟수 카운트
            if (cnt % k == 0) {
                result += secondMax; // 두 번째로 큰 수는 한 번만 더해도 됨
            } else {
                result += firstMax; // 첫 번째로 큰 수 더하기
            }
        }
        System.out.println(result);
    }
}

두 번째 풀이의 if (cnt % k == 0) 이 부분을 보고 순간 짜릿했다. 나는 일차원적으로 if (cnt == k) 이렇게만 생각하고 cnt를 0으로 초기화해줬는데 cnt가 계속 증가하면서 k의 배수가 되면 두 번째로 큰 수를 더해주고 그렇지 않으면 첫 번째로 큰 수를 더해주면 되는 것이었다!

세 번째 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 큰수의법칙 {
    static int n, m, k;
    static int[] numArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 수의 개수
        m = Integer.parseInt(st.nextToken()); // 더하는 횟수
        k = Integer.parseInt(st.nextToken()); // 연속해서 더할 수 있는 횟수
        numArr = new int[n]; // n개의 자연수
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numArr.length; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numArr); // 오름차순 정렬
        int firstMax = numArr[numArr.length - 1]; // 첫 번째로 큰 수
        int secondMax = numArr[numArr.length - 2]; // 두 번쨰로 큰 수
        System.out.println(maxNum(firstMax, secondMax));
    }

    public static int maxNum(int firstMax, int secondMax) {
        int cnt = 0;
        int result = 0;
        for (int i = 0; i < m; i++) {
            cnt++; // 더하는 횟수 카운트
            if (cnt % k == 0) { // cnt는 증가하여 k의 배수가 됨
                result += secondMax; // 두 번째로 큰 수는 한 번만 더해도 됨
            } else {
                result += firstMax; // 첫 번째로 큰 수 더하기
            }
        }
        return result;
    }
}

마지막으로 큰 수의 법칙에 따라 답을 구하는 로직을 메소드로 분리하였다. 이전에는 main 메소드에 다 때려박았는데 앞으로는 최대한 기능별로 메소드를 분리해서 구현해보려 한다.