[D3] 최고의 쌍 - 9839 (Java)

문제 요약

N개의 양의 정수가 주어졌을 때, 이들 중 정확히 서로 다른 두 개의 정수 쌍을 고르려고 한다.

이때, 두 정수를 고르는 데 있어서 특별한 제약 조건이 존재한다.
고른 서로 다른 두 정수를 x, y라고 하면, 두 정수의 곱 x*y는 10진수로 읽었을 때 증가하면서도 연속한 숫자들로 이루어져야 한다.
예를 들어 2, 23, 23456, 56789는 제약 조건을 만족하고, 21, 54321, 67890, 89012, 88, 889, 79는 제약 조건을 만족하지 않는다.

이 조건을 만족하는 모든 쌍 중, 두 정수의 곱이 최대화되는 쌍을 “최고의 쌍”이라고 부른다.
최고의 쌍이 존재하는지, 존재한다면 이 쌍의 곱은 얼마인지 계산하는 프로그램을 작성해보자.

---

문제 분석

숫자들을 받아서 최댓값을 기준으로 정렬하고, 순서대로 두 쌍을 골라 곱한 후, 그 값이 최고의 쌍인지 구하기.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append(" ");
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            List<Integer> numList = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                numList.add(Integer.parseInt(st.nextToken()));
            }
            // 숫자를 큰 수부터 정렬해야 가장 큰 값을 빨리 찾기 쉽다.
            Collections.sort(numList, Collections.reverseOrder());
            int maxValue = -1; // 디폴트값
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    int mulValue = numList.get(i) * numList.get(j);
                    if (checkSequence(mulValue)) {
                        maxValue = Math.max(maxValue, mulValue);
                    }
                }
            }
            sb.append(maxValue).append("\n");
        }
        sb.deleteCharAt(sb.length()-1); // sb사용시 가장 마지막에 \n이 들어가면 틀림.
        System.out.println(sb.toString());
    }

    // 해당 숫자가 10진수로 증가하면서 연속적인 수인지 판단
    private static boolean checkSequence(int num) {
        // 가장 끝 자리 숫자를 저장
        int prevDigit = num % 10;
        num /= 10;
        while (num > 0) { // 해당 숫자를 기준으로 순차적으로 다음 숫자가 작아지는지 확인
            int curDigit = num % 10;
            if (curDigit != prevDigit - 1) {
                return false;
            }
            prevDigit = curDigit;
            num /= 10;
        }
        return true;
    }
}

---