[알고리즘 PS] 백준 9440번 숫자 더하기 자바 문제풀이

문제

해당 포스팅은 백준의 9440번 숫자 더하기 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

9440번: 숫자 더하기

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이번 문제는 정렬과 그리디를 적절하게 사용해야 하는 문제이다.

 

문제에서 핵심은

숫자를 정렬하고 0 ~ 숫자 배열 길이만큼 반복하며 서로 다른 두 수에 마지막 자리에 추가 해주는 것

이것이 핵심이다.

 

예를 들어 1 2 7 8 9 라는 수가 있다고 해보자.

 

그럼 위의 핵심대로 문제를 풀면 다음과 같은 형식이 될 것이다.

arr = 1, 2, 7, 8, 9;// 정렬된 상태

// 첫 단계
num1 = 1
num2 = 2

// 두 번쨰
num1 = 1, 7
num2 = 2, 8

// 세 번째
num1 = 1, 7, 9
num2 = 2, 8;

이런식으로 해서 최종적으로 num1 + num2 를 수행해야 최솟값이 나온다.

오답 후보

하지만 이들 사이에 0이 있는 경우를 생각해보자.

 

0이 있는 경우 정렬을 한다면 arr = 0 1 2 3 4 0 1 2 3; 에서 arr = 0 0 1 1 2 2 3 3 4; 가 된다.

 

이대로 정답을 출력한다면 0으로 시작하는 수가 생기게 되고, 그러면 AC를 받을 수 없다.

 

이렇게 0이 있는 경우에는 0을 처음으로 등장하는 수 뒤로 숨겨줘야 한다.

 

arr = 0 0 1 1 2 2 3 3 4; 에서 arr = 1 1 0 0 2 2 3 3 4;

이런 로직을 추가하면 정답이 된다.

나는 해당 연산을 위해서 0이 등장한 횟수에서 + 2만큼 오른쪽으로 shift 연산 을 하였다.

만약 쉬프트 연산을 알지 못한다면 자바로 알고리즘에서 자주 사용되는 배열 shift 구현하기 을 참고하는 것이 좋을 것 같다.

 

정답 코드

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while(true) {
            String[] ns = br.readLine().split(" ");
            if(ns.length == 1 && ns[0].equals("0")) break;

            int n = Integer.parseInt(ns[0]);

            int[] arr = new int[n];

            int zeroCount = 0;
            for(int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(ns[i+1]);
                if(arr[i] == 0) zeroCount++;
            }

            Arrays.sort(arr);

            if(zeroCount > 0) {
                int[] tempArr = new int[zeroCount + 2];

                for(int i = 0; i < zeroCount + 2; i++) {
                    tempArr[i] = arr[i];
                }
                leftShift(tempArr);

                for(int i = 0; i < zeroCount + 2; i++) {
                    arr[i] = tempArr[i];
                }
            }

            StringBuilder num1 = new StringBuilder();
            StringBuilder num2 = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                if(i % 2 == 0) num1.append(arr[i]);
                else num2.append(arr[i]);
            }

            int n1 = Integer.parseInt(num1.toString());
            int n2 = Integer.parseInt(num2.toString());

            bw.write((n1 + n2) + "\n");
            bw.flush();
        }
        bw.close();
    }

    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    private static void reverse(int[] arr, int start, int end) {
        end = end - 1;
        while(start < end) {
            swap(arr, start, end);
            start++;
            end--;
        }
    }

    private static void leftShift(int[] arr) {
        int size = arr.length;
        reverse(arr, size - 2, size);
        reverse(arr, 0, size - 2);
        reverse(arr, 0, size);
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.