JAVA 백준 17298 오큰수 (스택 2)

https://www.acmicpc.net/problem/17298

 

---

문제

1. 첫째 줄에 수열 A의 크기 N(1 <= N <= 1000000) 입력.
2. 둘째 줄에 수열 A의 원소 (1 <= 각 원소 <= 1000000)을 공백으로 구분하여 N개 입력.
3. 자신보다 오른쪽에 있으면서 가장 왼쪽에 있는 큰 수를 오큰수라고 함. 그러한 수가 없는 경우 오큰수는 -1.
4. N개의 오큰수를 공백으로 구분하여 출력.

---

 

초기 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Objects;
import java.util.Stack;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(br.readLine());
        int count = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        Stack<Integer> stack = new Stack<Integer>();

        Integer[] result = new Integer[N];

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            stack.push(num);

            for (int j = 0; j < i; j++) {
                if ((stack.get(j) < num)  && (result[j]==null)) {
                    result[j] = num;
                }
            }
        }

        for (Integer i : result) {
            if (i == null) {
                sb.append("-1 ");
            } else {
                sb.append(i).append(" ");
            }
        }

        System.out.println(sb);
    }
}

 

스택에 저장된 수보다 방금 입력한 수가 클 때 배열에 입력된 수 저장.
배열에서 수가 입력된 곳은 제외하고 null인 나머지 부분만 비교한다.

출력 시 null인 부분을 -1으로 바꿔 출력.

 

아~~~ 아쉽게 시간초과 사실 처음부터 시간초과가 났어요 어렵다

 

그러면. 발상의 전환이 필요함.

1번부터 비교해서 시간 초과가 난 거라면... top부터 비교할 방법을 찾아야 됨. 또 코드 갈아엎기 시작...

 

새로운 방식의 코드~

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Objects;
import java.util.Stack;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(br.readLine());
        int max = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        Stack<Integer> stack = new Stack<Integer>();

        Integer[] result = new Integer[N];

        for (int i = 0; i < N; i++) {
            stack.push(Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < N; i++) {
            if (i == 0) {
                max = stack.pop();
                sb.append("-1 ");
            } else {
                int num = stack.pop();
                if (max <= num) {
                    max = num;
                    sb.insert(0,"-1 ");
                } else {
                    sb.insert(0," ").insert(0,max);
                    if(!stack.isEmpty() && num>stack.peek()){
                        max = num;
                    }
                }
            }
        }

        System.out.println(sb);
    }
}

 

이번에는 스택에 숫자를 다 채우고 맨 위에서부터 빼면서 비교하는 방식입니다.

이전 코드는 중첩된 반복문이 있었기 때문에 이번엔 시간이 많이 줄었을 거라 생각됩니다.

아 아니... 왜? 좀 잘했다고 생각했는데... 흠.

아!

 

배열 만들어놓고 안 썼네 써야겠군...

 

마지막 문제 이어서 진행합니당...

진짜 많은... 수정을 했어요 진짜...
아무래도 답이 맞아야 제출을 하니까 저 하나하나에도 수많은 노력과 고생이 있었답니다...
아무튼 결국은... 맞았습니다.

채점이 진짜 진짜 진짜 오래 걸렸어요 그치만... 맞았어요
맞으면 된 거임 될 때까지 했잖아 내 노력과 끈기가 이긴 거야 됐어
아무튼...

 

최종 코드!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        Stack<Integer> stack = new Stack<Integer>();

        Integer[] result = new Integer[N];

        for (int i = N - 1; i >= 0; i--) {
            result[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            if (i == 0) {
                stack.push(result[i]);
                result[i] = -1;
            } else {
                while (!stack.isEmpty() && result[i] >= stack.peek()) {
                    stack.pop();
                }
                if (i < N - 1 && !stack.isEmpty() && result[i] > result[i + 1]) {
                    stack.push(result[i]);
                    result[i] = stack.get(stack.size() - 2);
                } else {
                    if (!stack.isEmpty() && result[i] < stack.peek()) {
                        result[i] = stack.peek();
                    } else {
                        stack.push(result[i]);
                        result[i] = -1;
                    }
                }
            }
        }

        for (int i = N - 1; i >= 0; i--) {
            sb.append(result[i]).append(" ");
        }

        System.out.println(sb);
    }
}

 

배열에서 큰 값을 스택에 차곡차곡 넣어 비교하고 더 작거나 같으면 스택에서 꺼내 더 큰 수를 찾아 배열에 다시 숫자를 저장.

 

감격의 추가 컷...