글 읽기 - [JAVA] 맞추었으나 시간초과 관련해서 질문

yujun93 3년 전 0

LowerBounnd를 사용해서 문제 접근을 하여 풀었으나 자꾸 시간초과가 났었습니다.

다른 분들의 질문글을 보다가 변수 메모리 관련한 문제인것 같아 자주 접근하는 int배열 arr와 result 그리고 int형인 idx를 static 으로 정적 멤버 변수로 선언했습니다. 그런데도 시간초과가 났었습니다.

다시 확인하고자 다른 분들의 문제푼것과 비교했을때 차이점이 크게 없었습니다.

다만 mid라는 int형 변수를 선언한 위치에 따라 결과가 다르게 나왔습니다.

다시 소스코드를 처음으로 돌려 mid 변수 위치만 다르게 하여 제출해 보았습니다.

mid라는 변수는 while문이 돌때마다 값이 변하기 때문에 while문 밖에서 선언했더니 시간초과나고 while문 안에서 선언했을시는 정답이 맞습니다.

무슨 이유로 이렇게 갈리는건지 궁금합니다.
while문 안에서 선언하거나 밖에서 선언하든 어차피 리터럴형이라 값이 변할때마다 새로운 변수주소가 생성되는것이 아닌가요???

어떤 부분이 부족한지 잘 모르겠습니다 ㅠㅠ

import java.io.*;
import java.util.StringTokenizer;

public class Main {

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

        int n = Integer.parseInt(rd.readLine());
        StringTokenizer st = new StringTokenizer(rd.readLine());
        int[] arr = new int[n];
        int[] result = new int[n];
        int j = 0;
        int idx = 0;

        while (st.hasMoreTokens()) {
            arr[j] = Integer.parseInt(st.nextToken());
            j++;
        }

        result[0] = arr[0];
        idx = 0;

        for (int i = 1; i < n; i++) {
            if (result[idx] < arr[i]) {
                result[++idx] = arr[i];
            } else if (result[idx] > arr[i]) {
                int start = 0;
                int end = idx;
                int mid = (start + end) / 2; // mid를 while문 밖에 선언시 시간초과

                while (start < end) {
                    //int mid = (start + end) / 2; mid를 while문 안에 선언시 정답

                    if (arr[i] > result[mid]) {
                        start = mid + 1;
                    } else {
                        end = mid;
                    }
                }

                result[end] = arr[i];
            }
        }

        wt.write(String.valueOf(idx + 1));

        wt.flush();
        wt.close();
    }
}

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