[자바] 백준 9440 - 숫자 더하기 (java)

 문제 : boj9440

---

 

필요 알고리즘 개념

• 정렬 + 그리디
  
  • 정렬을 통해 매번 낮은 수 부터 확인하는 그리디 개념으로 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이 문제에서 가장 처리하기 까다로운 부분은 두 수가 0으로 시작하면 안된다는 점이다. 그러니 우선 입력값에 0이 없다고 생각하고 한번 생각해보자.

 

  1,2,7,8이 있다면 두 수를 어떻게 정해야 할까?

중요한건 각 자리수에 어떤 수 2개를 사용할지이다. 무슨말이냐면,

17 + 28과 18 + 27의 합은 같다. 즉 두 수의 합이 중요한게 아니고, 각 자리수에 어떤 2개의(혹은 홀수개라면 1개의)숫자가 와야할지가 중요한 것이다.

 

  그렇다면 당연히 더 높은 자리수에 작은 숫자가 오는 것이 결과가 작아질 것이다. 따라서 로직은 다음과 같이 세워볼 수 있다. 답을 구하는 변수를 answer이라고 하겠다.

1. 입력으로 들어온 숫자를 정렬한다.

2. N이 짝수라면 매번 각 자리마다 2개씩 선택해주면 된다. N이 홀수라면 우선 가장 작은 수 하나를 answer에 더해주고, 10을 곱해준다(가장 높은 자리수에 해당한다. 10을 곱한건 자리수를 하나 올려준 것이다.)

3. 이후 남은 숫자는 짝수는 0개, 홀수는 1개를 '2'에서 이미 넣었으므로 짝수이다. 그러므로 이후 로직은 동일하다. 남은 수가 없을 때 까지 가장 작은 수 2개를 뽑아 answer에 더해주고, 마지막만 제외하고 매번 10을 곱해주면 된다.

 

  예를들어 1,2,7,8,9를 보자.

1. 정렬해도 동일한다.

2. N이 홀수이므로 answer에 가장 작은 1을 더해주고 10을 곱해준다. answer = 10

3. 2개를 뽑아 answer에 더해주고 10을 곱해준다. answer = (answer + 2 + 7) * 10 이므로, answer = 190이 된다.

    아직 남은게 2개 있으므로 마찬가지로 진행한다. answer = (190+8+9) * 10 = 2070이 되는데, 더이상 남은게 없으므로       10은 안곱해도 된다. 따라서 207이 답이다.

 

----

 

  그럼 이제 위 로직에서 0이 추가된걸 넣어주면 된다. 약간 더 복잡해지지만, 위에서 로직을 확고히 설정했다면 크게 문제될건 없다. 내 경우엔 정렬 후 0이 아닌 가장 작은 수를 찾기 귀찮아서 그냥 0이 주어진 횟수는 변수 zeroCnt에 세줬다.

A. 0을 제외한 나머지 수를 정렬한다.

B. 위 로직의 '2'처럼 N에서 0의 갯수를 제외한 나머지가 홀수, 짝수에 따라 가장 큰 자리수를 처리해준다.

C. 두 숫자의 가장 큰 자리수가 0이 되면 안된다. 따라서 0이 하나라도 있다면 우선 큰 자리수부터 처리해주자. 이 때 'B'에서 홀수라면 1개의 수는 이미 처리했으므로 1개의 수만 처리해주면 된다. 짝수였다면 처리된게 아직 없으므로 2개의 수를 처리해준다 이 때 '0이 아닌 수가 최소 2개 이상 존재한다' 라고 했으므로 2개가 없는 것에 대한 예외처리는 필요없다.

D. 다음으로 숫자 0들을 모두 처리해준다. 2개씩 빼주면서 자리수가 늘어날 것이다. 남는게 하나 있는 경우도 마찬가지로 처리해준다.

E. 이제 남은 경우는 위에서 얘기했던 '3' 로직 뿐이므로, 똑같이 처리해주면 된다.

 

이하 코드의 getAnswer에 주석이 달려있으니 잘 이해가 안된다면 코드로 한번 확인해보자.

 

어쨌든 이 문제에서 중요한 점은, 작은 수가 더 높은 자리수에 쓰일 수록 결과 합은 작아진다. 단, 0으로 시작하면 안된다. 그리고 두 수가 각각 뭐인지는 중요하지 않다. 각 자리수에서 어떠한 수를 1개(N이 홀수일 경우 가장 큰 자리수에서만) 혹은 2개 고르는지가 중요하다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    private long getAnswer(int n, int zeroCnt, ArrayList<Integer> arr) {
        Collections.sort(arr);

        // 남은 갯수를 짝수로 만들어줌
        long answer = n%2 == 0 ? 0 : arr.get(0)*10;
        int idx = n%2 == 0 ? 0 : 1;

        // 숫자의 처음이 0이 되지 않도록 예외처리 해줌
        if (zeroCnt>0) {
            if (n%2 == 0) {
                answer += arr.get(idx) + arr.get(idx+1);
                idx += 2;
            } else {
                answer += arr.get(idx);
                idx += 1;
                zeroCnt-=1;
            }
            answer*=10;
        }

        // 남은 '0' 처리
        while (zeroCnt >= 2) {
            answer*=10;
            zeroCnt-=2;
        }
        if (zeroCnt == 1) {
            answer += arr.get(idx);
            answer*=10;
            idx++;
        }

        // 이하 숫자의 첫 시작이 0으로 시작되지 않으며, 남은 수는 짝수이므로 자리수마다 2개씩 골라주면 끝임.
        for (;idx < arr.size(); idx+=2) {
            answer += arr.get(idx) + arr.get(idx+1);
            answer*=10;
        }
        return answer/10;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            if (n == 0) break;
            ArrayList<Integer> arr = new ArrayList<>();
            int zeroCnt = 0;
            for (int i = 0; i < n; i++) {
                int cur = Integer.parseInt(st.nextToken());
                if (cur == 0) {
                    zeroCnt++;
                    continue;
                }
                arr.add(cur);
            }
            sb.append(getAnswer(n, zeroCnt, arr)).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}