[SWEA] 6190. 정곤이의 단조 증가하는 수

문제

정곤이는 자신이 엄청난 수학자임을 증명하기 위해, 어떤 규칙 만족하는 수를 찾아보기로 했다.

그 규칙은 단조 증가하는 수인데, 각 숫자의 자릿수가 단순하게 증가하는 수를 말한다.

어떤 k자리 수 X = d1d2…dk 가 d1 ≤ d2 ≤ … ≤ dk 를 만족하면 단조 증가하는 수이다.

예를 들어 111566, 233359는 단조 증가하는 수이고, 12343, 999888은 단조 증가하는 수가 아니다.

양의 정수 N 개 A1, …, AN이 주어진다.

 1 ≤ i < j ≤ N 인 두 i, j에 대해, Ai x Aj값이 단조 증가하는 수인 것들을 구하고 그 중의 최댓값을 출력하는 프로그램을 작성하라.

 

풀이방법

완전탐색으로 해결

 

n개의 숫자가 입력으로 주어졌을 때, 각 숫자의 곱이 단조 숫자인 값을 모두 구하고 

 

이 숫자들 중 최대값을 출력한다.

 

소스코드

package samsung;

import java.util.*;

public class s_6190 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int[] a = new int[n];
			int max = -1;
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = i + 1; j < n; j++) {
					int val = a[i] * a[j];
					String s = String.valueOf(val);
					int flag = 0;
					for(int k = 1; k < s.length(); k++) {
						if(s.charAt(k-1) > s.charAt(k)) {
							flag = 1;
							break;
						}
					}
					if(flag == 0)
						max = Math.max(max, val);
				}
			}
			System.out.println("#" + t + " " + max);
		}
	}
}