[JAVA] [SWEA] 9839. 최고의쌍

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

 

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

 

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

 

1. 정수 중 중복하지 않게 2개를 뽑는다.

2. 곱하여 연속하면서 증가하는지 확인한다.

3. 연속하면서 증가하는 수 중에서 가장 큰 수를 확인힌다.

 

처음에는 제한시간 초과가 났었는데 그 이유를 잘 모르겠다.

 

처음 시도한 방식은 곱한 두 수를 String으로 바꾸어 한칸씩 들고와 비교를 하는 방식이었는데...

 

사실 시간 복잡도 상으로는 아무 문제가 없으니 문제 될것이 없다 생각했었다.

 

밑에 방식으로 푼 것이나 String으로 바꾸어 한칸씩 자르면서 검사 해본 것이나

 

사실상 모든 것을 검사해본다면 같은 시간복잡도가 소모 되고

 

String을 다시 Integer로 바꾸는데 시간만 걸릴텐데 아무래도 그거 차이라기에는 너무 이상한 것 같다...

 

회사에 입사한 후에 코딩을 안하다 보니

 

다시 코딩하는게 버거워 쉬운 것부터 다시 시작하는데 그마저도 머리가 굳어 힘든 것 같다. ㅠㅠ

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; ++t) {
			int n = Integer.parseInt(br.readLine());
			String[] str = br.readLine().split(" ");
			int[] arr = new int[str.length];
			for(int i=0; i<arr.length; ++i) {
				arr[i] = Integer.parseInt(str[i]);
			}
			int maxMulti = -1;
			for(int i=0; i<arr.length-1; ++i) {
				int x = arr[i];
				for(int j=i+1; j<arr.length; ++j) {
					int y = arr[j];
					int z = x * y;
					int num = z % 10;
					z /= 10;
					boolean check = true;
                    
					while(z > 0){
						if(num - 1 == z%10){
							num--;
						}else{
							check = false;
							break;
						}
						z /= 10;
					}
					if(check && maxMulti < x*y){
						maxMulti = x*y;
					}
				}
			}
			bw.write("#"+t+" "+maxMulti+"\n");
		}
		br.close();
		bw.close();
	}

}