글 읽기 - 더 시간을 줄일 수 있는 방법이 있을까요? 자바입니다.

tna1595 5년 전 0

온전히 브루탈 포스로 모두 하나하나 계산하다가,

계산할 필요가 없는 식에 대해서는 점프하는 방식으로 바꿨는데요. 또한

너무 큰 값에 대해서는(9876543210) 그냥 조건문에서 거르게 했고요.

이렇게 하면 콘솔에서 직접 돌릴때는 1초는 커녕 0.1초도 안걸리는 속도로 돌아가는 것 같은데

제출을 하면 97%즈음에서 시간초과로 항상 틀리네요.. 더 좋은 방법이 있을까요?

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int count = 0;
        if (N > 1022) bw.write("-1");
        else if(N == 1022) bw.write("9876543210");
        else {
            for (int i = 1; ;) {

                boolean isGood = true;
                int past = -1;
                int tmp = i;
                int jump = 1;
                while (tmp != 0) {
                    int value = tmp % 10;
                    if (value <= past) {
                        isGood = false;
                    }

                    if(!isGood && value > past){
                        break;
                    }

                    jump *= 10;
                    past = value;
                    tmp /= 10;
                }
                if (isGood) {
                    count++;
                    if (count == N) {
                        bw.write(Integer.toString(i));
                        break;
                    }
                    i++;
                } else {
                    i += jump/10 ;
                    i -= (i % (jump / 10));
                }
            }
        }

        bw.flush();
        bw.close();
    }
}

112224 5년 전 2

설명이 있었으면 좀 더 좋았을텐데 아쉽네요 ㅠㅠ

일단 시간초과의 원인에 대해 살펴보자면 987 다음의 감소하는 수는 3210 인데 이를 1000 -> 1100 -> 1110 ... 순으로 탐색하다보니 연산횟수가 굉장히 많아지게 됩니다.

3210 다음에 4320을 갈때도 4000->4100->4110....

몇자리 수인지를 체크해주시고 이를 이용하시는게 시간단축의 중요개념이 될 것 같습니다!

tna1595 5년 전 0

감사합니다. 다음 질문부터는 주석을 좀 더 적겠습니다 ㅠㅠ

이해가 됬습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

더 시간을 줄일 수 있는 방법이 있을까요? 자바입니다.

tna1595 5년 전 0

112224 5년 전 2

tna1595 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말