[자바] 백준 21740 - 도도의 수학놀이 (java)

 문제 : boj21740

---

 

필요 알고리즘 개념

• 그리디, 정렬, 문자열
  
  • 그리디로 풀 수 있는 문제이다. 다만 플래문제답게 세세하게 예외를 생각해봐야하고, 구현이 좀 까다로울 수 있다.

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

 

---

 

풀이

  사실 이 문제가 플래인 이유는 '단 한 번, 한 수를 두 번 사용할 수 있다.' 이것 때문이다. 아마 저 조건이 없었으면 실버급이었을 것 같다.

 

  그러므로 우선 '단 한 번, 한 수를 두 번 사용할 수 있다.' 이걸 생각하지 않은상태에서 어떻게 풀지 생각해보자. 이건 쉽게 생각할 수 있다. 입력받은 수를 미리 180도 회전시켜둔다. 아래와 같이 처리하면 될 것이다.

class Number {
    String original, reverse;

    public Number(String str) {
        original = str;

        StringBuilder sb = new StringBuilder();

        for (int i = str.length()-1; i >= 0; i--) {
            char c = str.charAt(i);
            switch (c) {
                case '6': c = '9'; break;
                case '9': c = '6'; break;
            }
            sb.append(c);
        }
        reverse = sb.toString();
    }
}

  

  그리고 아래와 같이 정렬하기만 하면 끝난다. 180도 회전시킨걸 기준으로 정렬한 후, 원래의 문자열을 순서대로 출력해주는 것이다. 이 때 두 문자를 합쳐서 비교해주는 이유는 예를들어 180도 회전한 결과가 '13'과 '131'인 값을 비교한다고 해보자. 뭐가 더 큰지 비교하기 위해서는 둘 중 뭐가 더 앞에 와야 더 큰 수가 되는질 봐야된다. 즉, '13131' vs '13113'을 비교해줘야 한다. 따라서 아래와 같이 비교해야 한다.

Arrays.sort(arr, new Comparator<Number>() {
    @Override
    public int compare(Number o1, Number o2) {
        return (o2.reverse+o1.reverse).compareTo(o1.reverse+o2.reverse);
    }
});

 

 

 

  그럼 이제 '단 한 번, 한 수를 두 번 사용할 수 있다.' 을 생각해보자. 아래와 같은 입력을 보자.

2
10 6

이 경우 단순히 위에서 정렬한 순서대로 큰걸 2번 출력하겠다고 생각하면 틀리게 된다. 위와 같은 입력의 경우 180도 회전하면 각각 '01'과 '9'가 된다. 따라서 '9'가 더 크다고 판단되므로 '1066'이 답일 것 같다. 하지만 실제 답은 '10106'이다. 당연히 자리수가 큰게 먼저이기 때문이다. 따라서 이번엔 정렬 방식이 위와 달라야한다. 단순히 뭐가 먼저 오는게 좋냐가 아니라, 180도 회전한 수 기준으로 가장 큰 자리수가 큰 값들 중에서 가장 큰 수를 찾아야 한다. 따라서 아래와 같이 정렬한다. dup에 두번 나와야 하는 수의 주소값을 기록해둔다.

Arrays.sort(arr, new Comparator<Number>() {
    @Override
    public int compare(Number o1, Number o2) {
        if (o2.len == o1.len)
            return o2.factor.compareTo(o1.factor);
        return o2.len - o1.len;
    }
});
Number dup = arr[0];

 

  그리고 위에서 설명한 '단 한 번, 한 수를 두 번 사용할 수 있다.' 조건을 제외한 나머지 부분을 처리해주고 dup의 주소값에 해당하는 값만 두번 출력해주고 나머진 순서대로 출력해주면 된다.

Arrays.sort(arr, new Comparator<Number>() {
    @Override
    public int compare(Number o1, Number o2) {
        return (o2.reverse+o1.reverse).compareTo(o1.reverse+o2.reverse);
    }
});
for (int i = n-1; i >= 0; i--) {
    answer.append(arr[i].original);
    if (arr[i] == dup)
        answer.append(arr[i].original);
}

 

 

---

 

코드 : github

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

class Number {
    private static final int MAX_LEN = 7;
    String original, reverse, factor;
    int len = 0;

    public Number(String str) {
        original = str;

        StringBuilder sb = new StringBuilder();

        for (int i = str.length()-1; i >= 0; i--) {
            char c = str.charAt(i);
            switch (c) {
                case '6': c = '9'; break;
                case '9': c = '6'; break;
            }
            sb.append(c);
        }
        reverse = sb.toString();

        len = sb.length();
        int appendZeroCnt = MAX_LEN - len;
        while (appendZeroCnt-->0)
            sb.append('0');
        factor = sb.toString();
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<13);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        Number[] arr = new Number[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[i] = new Number(st.nextToken());

        StringBuilder answer = new StringBuilder();

        Arrays.sort(arr, new Comparator<Number>() {
            @Override
            public int compare(Number o1, Number o2) {
                if (o2.len == o1.len)
                    return o2.factor.compareTo(o1.factor);
                return o2.len - o1.len;
            }
        });
        Number dup = arr[0];

        Arrays.sort(arr, new Comparator<Number>() {
            @Override
            public int compare(Number o1, Number o2) {
                return (o2.reverse+o1.reverse).compareTo(o1.reverse+o2.reverse);
            }
        });
        for (int i = n-1; i >= 0; i--) {
            answer.append(arr[i].original);
            if (arr[i] == dup)
                answer.append(arr[i].original);
        }


        System.out.println(answer);
    }
}