Q. 6190. 정곤이의 단조 증가하는 수(D3)

Q. 6190. 정곤이의 단조 증가하는 수(D3)

 

0. 문제

 

D3 난이도의 문제이고, 구현 문제라고 생각된다.

단조 증가하는 수는 각 숫자의 자릿수가 단순하게 증가하는 수를 말한다.

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

수열이 주어졌을 때 두 원소의 곱이 단조 증가하는 수인지 판단해서그중에 최대값을 출력하는 문제이다.

---

1. 풀이

1. 두 수를 곱한 뒤에 그 수가 단조 증가하는 수인지 판단한다.

2. 만약 단조 증가하는 수인 경우 최대값을 갱신한다

import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
class Solution
{
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int[] inputNum;
    static int N, Max;
     
    static void input() throws IOException
    {
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        inputNum = new int[N];
        for (int i = 0; i < N; i++) {
            inputNum[i] = -Integer.parseInt(st.nextToken());
        }
    }
     
    static void pro(int tc) {
         
        Max = -1;
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                int num = inputNum[i] * inputNum[j];
                if (check(num)) {
                    Max = Math.max(Max, num);
                }
            }
        }
        sb.append(String.format("#%d %d\n", tc, Max));
    }
     
    static boolean check(int num) {
         
        int prevNum = 9;
        int curNum;
         
        while (num != 0) {
            curNum = num % 10;
            if (curNum > prevNum) {
                return false;
            }
            num /= 10;
            prevNum = curNum;
        }
        return true;
    }
     
     
    public static void main(String args[]) throws Exception
    {
         
        //br = new BufferedReader(new FileReader(new File("res/input.txt")));
        br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int test_case = 1; test_case <= T; test_case++)
        {
            input();
            pro(test_case);
        }
        System.out.println(sb);
    }
}

---

2. 시간복잡도 계산

 

0) N의 최대값은 1000이고, 수열의 원소는 30000 이하이다.

1) 수열 저장 - O(N)

2) 풀이 1번 - O(N* (N - 1))

따라서 시간복잡도는 약 O(N^2)이고, 시간제한은 2초이므로

1초에 약 1억번 연산을 한다고 가정하면, 1초 이내에 풀 수 있다.

---