[이것이 코딩 테스트다.Part02.Chapter03] - 큰 수의 법칙 (Java)

---

안녕하세요.
지금까지 계속 저만의 기술 블로그를 만들어야지, 만들거야
마음으로만 다짐하다가 인제야 시작하게 되었습니다.
비록 시작은 코딩일기지만, 그 끝은 창대하게
어엿한 개발자 블로그로 성장할 수 있도록 노력하겠습니다.

---

Prologue

안녕하세요!
나동빈 저자의 [이것이 코딩 테스트다] 라는 교재로 알고리즘 스터디를 개설하고 진행중이어서 해당 교재에 있는 문제들은 풀어보고 하나씩 블로그에 정리하려고 합니다. 알고리즘 포스트는 시간이 생각보다 오래걸려 저도 모르게 기피해왔네요..
이제부터 다시 한 문제씩 작성해보도록 하겠습니다!

[큰 수의 법칙]

<문제>
동빈이의 큰수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 방법이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고 K가 3이라고 가정하자.

이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고 K가 2라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다.

결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4 인 28이 도출된다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

<입력 조건>

• 첫째 줄에 N(2 <= N <= 1000), M(1 <= M <= 10000), K(1 <= K <= 10000) 의 자연수가 주어지며 각자연수는 공백으로 구분한다.

• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다.
  단, 각각의 자연수는 1 이상 10000 이하의 수로 주어진다.
  입력으로 주어지는 K는 항상 M보다 작거나 같다.

<출력 조건>

• 첫째 줄에 동빈이의 큰수의 법칙에 따라 더해진 답을 출력한다.

<입력 예시>                                                                             <출력 예시>

• 5 8 3                                                                                      46
  2 4 5 4 6

---

PseudoCode

처음 문제를 봤을 때 들었던 생각은

1. 수를 입력 받아 배열에 담는다.

2. 배열을 정렬하여 제일 큰 수와, 두 번째로 큰 수를 구한다.

3. 제일 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하기를 반복한다.

입니다.

첫 문제라 그런지 난이도가 쉬웠고 수도코드를 구현하는 것 만으로 해결이 가능했습니다.

---

SourceCode

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws Exception
    {
        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[] arr = new int[N];

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
        {
            arr[i] = Integer.parseInt(st2.nextToken());
        }

        Arrays.sort(arr);

        // 첫 풀이
        int count = 0;
        int sum = 0;

        for(int i = 0; i < M; i++)
        {
            int firstBig = arr[arr.length-1];
            int secondBig = arr[arr.length-2];
            count++;

            if( count % K == 0)
            {
                sum += secondBig;
            }else
            {
                sum+= firstBig;
            }
        }

        System.out.println(sum);

//        //해설 보고 수정한 풀이
//        int sum = 0;
//        int firstBig = arr[arr.length-1];
//        int secondBig = arr[arr.length-2];
//
//        sum = (((M / (K+1))) * (firstBig * K + secondBig))  + ((M % (K + 1)) * firstBig);
//
//        System.out.println(sum);
    }
}

(언제나처럼 코드리뷰! 부탁드립니다!)

최근 프로그래머스에서 문제를 풀었는데 프로그래머스는 함수 완성형 문제라서 입출력을 따로 관리하지 않아도 되어서 좋았습니다.. 백준 문제들을 풀때처럼 입출력을 하려니까 오랜만이라 그런지 다시 찾아보면서 감을 되찾는 좋은 계기가 되었습니다.

코드를 살펴보면,

---

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[] arr = new int[N];

우선 필요한 변수들을 몇 가지 선언 및 초기화하는 파트입니다.
값을 입력받을 때는 BufferedReader를 이용하였습니다.
2 4 5 4 6 이런식으로 값이 들어와서 이를 하나씩 떼어 배열에 넣어줄
StringTokenizer 또한 이용하였습니다.

변수들로는,

• 배열의 길이에 대한 변수 N
• 몇 번 더할지에 대한 변수 M
• 제일 큰 수를 최대 몇 번까지 더할 수 있는지에 대한 변수 K
• 변수들을 배열에 담을 arr[ ]

이 있습니다.

---

    StringTokenizer st2 = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++)
    {
        arr[i] = Integer.parseInt(st2.nextToken());
    }

    Arrays.sort(arr);
}

다음은 값들을 배열에 넣고 정렬하는 부분입니다.

1. 먼저 값들을 입력 받고 공백을 기준으로 나누어 배열 arr[ ]에 하나씩 집어 넣습니다.

2. Java에서 기본적으로 제공하는 Arrays.sort()을 이용하여 배열 arr[ ]을 오름차순으로 정렬하였습니다.(sort()의 기본이 오름차순으로 정렬)

---

// 첫 풀이
        int count = 0;
        int sum = 0;

        for(int i = 0; i < M; i++)
        {
            int firstBig = arr[arr.length-1];
            int secondBig = arr[arr.length-2];
            count++;

            if( count % K == 0)
            {
                sum += secondBig;
            }else
            {
                sum+= firstBig;
            }
        }

        System.out.println(sum);

//        //해설 보고 수정한 풀이
//        int sum = 0;
//        int firstBig = arr[arr.length-1];
//        int secondBig = arr[arr.length-2];
//
//        sum = (((M / (K+1))) * (firstBig * K + secondBig))  + ((M % (K + 1)) * firstBig);
//
//        System.out.println(sum);

마지막으로 이 문제를 해결하는 직접적인 부분입니다.

코드를 보면 아시겠지만 풀이가 2가지가 있습니다. 첫 풀이가 수도코드를 구현하여 푼 방식이고 두 번째 풀이는 교재에 나와있는 방식을 참고한 방식입니다.

첫 풀이는 수도코드를 그대로 구현하였기에 설명을 생략하고, 두 번째 풀이는
어차피 제일 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 거니까 이를 한 덩어리로 하여 M 번의 횟수동안 몇 덩어리가 나오는지를 구하고 한 덩어리가 채 안되는 나머지 횟수만큼 제일 큰 수를 더해주면 되는 방식입니다.
(글이 엉망이어서 한 번 천천히 생각해보시면 이해가 될겁니다..)

처음엔 이 두 번째 방식이 이 문제에만 적용가능한 조금은 지엽적인 풀이 방식이 아닌가 생각했는데 다시 생각해보니 이러한 접근 방식을 알아두면 비슷한 상황에서 비슷한 방식으로 접근 가능하겠다는 생각이 들어서 난이도는 쉬웠지만 매우 만족스러운 문제였습니다.

---

Epilogue

구현 난이도는 낮았지만 오랜만에 입출력을 다시 다뤄보고 (특히 BufferedReader 와 StringTokenizer를 이젠 정말 나름 자유롭게 쓸 수 있게 된 것 같습니다.) 새로운 접근 방식을 알게되어 좋았습니다.

코드에 대한 조언은 언제나 환영이며, 오히려 부탁드리겠습니다.