[SW Expert Academy] 정곤이의 단조 증가하는 수 (D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWcPjEuKAFgDFAU4&categoryId=AWcPjEuKAFgDFAU4&categoryType=CODE&problemTitle=%EC%A0%95%EA%B3%A4%EC%9D%B4%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

 

1. 처음 풀이

import java.util.Scanner;

class Solution {

	public static int max;
	public static int arr[];
	public static boolean check[];
	public static int ans[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {
			int n = sc.nextInt();

			max = -1;
			arr = new int[n];
			ans = new int[2];
			check = new boolean[n];

			for (int i = 0; i < arr.length; i++) {
				arr[i] = sc.nextInt();
			}

			comb(0);

			System.out.println("#" + tc + " " + max);

		}

	}

	public static void comb(int depth) {
		if (depth == 2) {
			int num = ans[0] * ans[1];

			boolean isPossible = true;

			String number = Integer.toString(num);

			for (int i = 0; i < number.length() - 1; i++) {
				if (number.charAt(i) > number.charAt(i + 1)) {
					isPossible = false;
					break;
				}
			}
			if (isPossible)
				max = Math.max(num, max);

			return;
		}

		for (int i = 0; i < arr.length; i++) {
			if (!check[i]) {
				check[i] = true;
				if (depth == 0)
					System.out.println("depth 0:" + i);
				if (depth == 1)
					System.out.println("depth 1:" + i);
				ans[depth] = arr[i];
				comb(depth + 1);
				check[i] = false;
			}
		}

	}
}

 문제점 : 2*4를 했으면

4*2는 확인할 필요가 없는데 한다.

 

 

 

1. 두 번째 풀이

import java.util.Scanner;

class Solution {

	public static int n;
	public static int[] arr;
	public static int[] ans;
	public static long max;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {
			n = sc.nextInt();
			arr = new int[n];
			ans = new int[2];

			max = -1;

			for (int i = 0; i < arr.length; i++) {
				arr[i] = sc.nextInt();
			}

			dfs(0, 0);

			System.out.println("#" + tc + " " + max);
		}

	}

	public static void dfs(int pos, int depth) {
		if (depth == 2) {
			long answer = 0;
			answer = ans[0] * ans[1];

			boolean isPossible = true;

			String result = Long.toString(answer);

			for (int i = 0; i < result.length() - 1; i++) {
				if (result.charAt(i) > result.charAt(i + 1)) {
					isPossible = false;
					break;
				}
			}

			if (isPossible) {
				max = Math.max(answer, max);
			}

			return;
		}

		for (int i = pos; i < n; i++) { // 2 *4를 했으면 다시 4*2 해줄 수 없어서 pos 사용
			ans[depth] = arr[i];
//			if (depth == 0)
//				System.out.println("depth 0:" + i);
//			if (depth == 1)
//				System.out.println("depth 1:" + i);
			dfs(i + 1, depth + 1);
		}
	}
}

조합을 한 번만 검사함으로써 효율성 증가