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

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d3/Q6190.java

n개의 수가 주어진다. 두 수를 곱한수가 단조 증가하는 수인 경우 그 최대값을 출력하여라.
단조 증가하는 수가 없다면 -1을 출력하여라.
단조 증가하는 수란 111122345 처럼 계속해서 증가하는 수다 1111144442, 12345675같은 수는
단조 증가하는 수가 아니다.

처음 생각

조합을 짜야하나 생각했지만 2개의 수만 곱하면 되므로 2중 반복문을 통해서 배열에 저장해둔 수들을 곱해주었다.

▶ 2중 반복문 구현시 각각의 변수를 i,j라 한다면 중복된 경우를 피하기 위해 j의 시작은 i+1부터 시작해 주면된다.

▶ 예를들어 1 2 3 4 가 주어졌다면 1*2나 2*1이나 같은 수이기 때문이다.

다음 생각

결과변수 result보다 두 수의 곱이 작다면 그 수가 단조 증가하는 수여도 결과값을 갱신할 필요가 없으므로 결과변수보다 두 수의 곱이 작은경우는 단조 증가하는 수 검사를 하지 않았다.

다다음 생각

반대로 두 수의 곱이 결과 변수보다 클경우 이 수가 단조 증가하는 수인지 검사를 해주었다.

▶ 나머지 연산을 통해서 확인하는 방법도 있겠지만 String으로 변환해서 앞에서부터 수를 확인해 감소하는 수가 있다면 false를 return하도록 하였다.

다다다음 생각

위의 확인 메소드가 true를 return 해주면 결과 변수 result를 갱신해주었다.

▶ 초기에 result 변수를 0으로 초기화 했었는데 문제상 증가하는 수가 없다면 -1을 출력해야하므로 -1 초기화로 바꿔주었다.

다다다다음 생각

위와같이 풀고나서 단조 증가하는 수를 찾는 방법을 나머지 연산으로 바꿔보았다. 문자열로 처리시에는 케이스가 많을경우 메모리와 시간이 더 걸리기 때문에 숫자로 처리를 해보았다. 결과는 아래와 같다.

▶ 

▶ 최적화의 중요성을 알 수 있었다.

방안

1) Java 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

package swexpert.d3;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Q6190 {     static int[] arr;     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int tc = Integer.parseInt(br.readLine());         for(int i=1;i<=tc;i++){             int n = Integer.parseInt(br.readLine());             arr = new int[n];             StringTokenizer st = new StringTokenizer(br.readLine());             for(int j=0;j<n;j++)                 arr[j] = Integer.parseInt(st.nextToken());               // 2개의 곱이므로 2중 포문을 이용해 구해보자.             // 두번째 곱해지는건 앞선것보다 인자가 크게한다(중복 방지)             // 전부 양수이므로 초기값은 -1(수가 없다면 -1 출력이라)             int result = -1;             for(int j=0;j<n;j++){                 for(int k=j+1;k<n;k++){                     // 결과 값보다 큰 값만 단조 증가 수 체크하자                     if(result<arr[j]*arr[k])                         if(solve(arr[j]*arr[k]))                             result = arr[j]*arr[k];                 }             }             System.out.println("#"+i+" "+result);         }     }       // 단조 증가하는 수 확인     private static boolean solve(int n){         int t = n%10;         n /=10;         while(n!=0){             if(n%10>t) return false;             t = n%10;             n /=10;         }         return true;     } }

2) Python 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

def solve(n):     t = n%10     n = int(n/10)     while n!=0:         if n%10>t:             return False         t = n%10         n = int(n/10)     return True   tc = int(input()) for z in range(1,tc+1):     n = int(input())     arr = list(map(int,input().split()))     result = -1     for i in range(n):         for j in range(i+1,n):             if result<arr[i]*arr[j]:                 if solve(arr[i]*arr[j]):                     result = arr[j]*arr[i]     print('#'+str(z),result)