[백준] 17298번 JAVA

어렵진 않은데 왜 정답률이

30프로밖에 안되지 하면서 풀었는데 

하 시간 초과가 오지게 난다..

 

리팩토링 전 코드

import java.io.*;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

public class Main {
    public static void main(String args[]) throws IOException, InterruptedException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(reader.readLine());
        String[] strArr = reader.readLine().split(" ");
//        StringBuilder result = new StringBuilder();
        int[] intArr = new int[num];
        int[] ansArr = new int[num-1];

        for(int i = 0; i < num; i++){
            intArr[i] = Integer.parseInt(strArr[i]);
        }
        for(int i = 0; i < num - 1; i++){
            Stack<Integer> tempStack = new Stack<>();
            int value = intArr[i];
            boolean isFind = false;

            for(int j = num-1 ; j > i; j--){
                tempStack.push(intArr[j]);
            }
            while(!tempStack.isEmpty()){
                int tempValue = tempStack.pop();
                if(value < tempValue){
                    ansArr[i] = tempValue;
                    isFind = true;
                    break;
                }
            }
            if(!isFind){
                ansArr[i] = -1;
            }
        }

        for (int i = 0; i < num-1; i++) {
            bw.write(ansArr[i] + " ");
        }
        bw.write("-1");
        bw.write("\n");

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

사실 이것도 여러 포인트 수정한 거긴 한데 그래도 시간 초과가 났다..

여기서 더 뺄만한? 단축할 만한게 뭐가 있을까 생각해 봤는데

 

예로

4

1 3 5 2

라는 입력이 들어왔을 때

for(int j = num-1 ; j > i; j--){
	tempStack.push(intArr[j]);
}

이부분에서 현재 

3의 오큰수를 찾는다고 했을 때 tempStack에 3보다 오른쪽에 있는 5와 2를 스택에 넣는 작업을 하는데

어차피 3보다 오른쪽에 있으면서 큰 수 중 가장 왼쪽에 있는 걸 찾는 거니까 2까지 스택에 넣을 필요도 없이 

그냥 오른쪽에 있는거 하나하나 비교하고 break 하는 게 더 낫겠다는 결론을 내려서 다시 짰다.

import java.io.*;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

public class Main {
    public static void main(String args[]) throws IOException, InterruptedException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(reader.readLine());
        String[] strArr = reader.readLine().split(" ");
//        StringBuilder result = new StringBuilder();
        int[] intArr = new int[num];
        int[] ansArr = new int[num-1];
//      숫자 배열에 넣는 작업
        for(int i = 0; i < num; i++){
            intArr[i] = Integer.parseInt(strArr[i]);
        }
        for(int i = 0; i < num - 1; i++){
            boolean isFind = false;
            for(int j = i+1; j < num; j++){
                if(intArr[i]< intArr[j]){
                    isFind = true;
                    ansArr[i] = intArr[j];
                    break;
                }
            }
            if(!isFind){
                ansArr[i] = -1;
            }
        }

        for (int i = 0; i < num-1; i++) {
            bw.write(ansArr[i] + " ");
        }
        bw.write("-1");
        bw.write("\n");

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

 

그렇게 짜서 5번 만에 진행 중 퍼센트가 뜨길래 되나 했더니 또 안되고요 ㅎㅎ

 

결국 검색해서 백준 님 풀이를 찾았다..

 

import java.io.*;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

public class Main {
    public static void main(String args[]) throws IOException, InterruptedException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(reader.readLine());
        String[] strArr = reader.readLine().split(" ");
//        StringBuilder result = new StringBuilder();
        int[] intArr = new int[num];
        int[] ansArr = new int[num];
//      숫자 배열에 넣는 작업
        for(int i = 0; i < num; i++){
            intArr[i] = Integer.parseInt(strArr[i]);
        }
        Stack<Integer> indexStack = new Stack<>();
        indexStack.push(0);
        for(int i = 1; i < num; i++){
           if(indexStack.isEmpty()){
               indexStack.push(i);
           }
           while(!indexStack.isEmpty() && intArr[indexStack.peek()] < intArr[i]){
               ansArr[indexStack.pop()] = intArr[i];
           }
           indexStack.push(i);
        }
        while (!indexStack.empty()) {
            // 반복문을 다 돌고 나왔는데 스택이 비어있지 않다면 빌 때 까지
            ansArr[indexStack.pop()] = -1;
            // stack에 쌓인 index에 -1을 넣고
        }

        for (int i = 0; i < num-1; i++) {
            bw.write(ansArr[i] + " ");
        }
        bw.write("-1");
        bw.write("\n");

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

일단 아이디어가 달랐던 게

내가 생각한 건 

입력받은 배열을 0부터 length까지 돌면서, 비교하며 큰 수가 있으면 break 하는 방식으로

최소 n 최대 n^2의 시간 복잡도를 갖게 되어 시간 초과가 낫던 것.

 

백준 님 코드를 보면

0에서 length까지 돌되

바로 오른쪽 숫자와 비교해서 오른쪽 숫자가 더 크면 정답 배열에 해당 숫자를 오큰 수로 입력,

작으면 pass 하고 스택에 집어넣는다.

결국 스택에는 아직 오 큰 수를 찾지 못한 애들만 남는 거고

for문안에서 length만큼 도는 동안 stack안에 남아있는 숫자들의 오큰 수도 계속 찾게 되는데

이는 n의 시간 복잡도를 갖게 된다.

 

실제로 내 코드와 백준 님 코드를 count변수를 넣어서 출력해봤을 때

숫자 비교 횟수에서 확연한 차이가 낫다.