[백준: 알고리즘_Java] 17298_오큰수

 

<문제>

 

---

<풀이>

아니...나는 처음에 그냥 배열에 넣어서 풀었는데.. 계속 시간초과가 뜸. 그래서 구글에 쳐봤는데 스택으로 하는 거더라... 배열로도 할 수 있는데 그것도 배열을 스택처럼 이용해서 푸는 거였음. 근데 스택으로 다시 이해하기가 너무 귀찮아서 그냥 못 본 척하고 내가 했던 대로 하는데.. 시간 줄일라고 별의 별 노력(버퍼로 받기...for 줄이기..등등)을 했지만. 계속 시간 초과가 뜨길래 그냥 스택으로 바꿔서 풀기로 결심함.

이제부터 한번 해보겠음. 으아아아악 머리아파. 구글에서 살짝 보고 넘긴걸 바탕으로 생각해 보겠음.

 

--이게 처음에 배열로 푼거. 

import java.util.*;
import java.io.*;
public class RightBig {
    public static void main(String[] args) throws IOException {
        //int 배열에 넣고 왼쪽부터 검사
        //자신보다 오른쪽 수와 비교, 자기가 더 작으면 RB배열에 넣고 break
        //RB배열 검사해서 0이면 -1로 바꾸기

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        //수열 A
        int[] input = new int[n];
        //RB배열(오큰수)
        int[] RB = new int[n];
        Arrays.fill(RB, -1);
        String[] str = br.readLine().split(" ");

        for(int i= 0; i<n; i++) {
            input[i] = Integer.parseInt(str[i]);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i <n; i++) {
            for(int j = i+1; j<n;j++) {
                if(input[i]<input[j]) {
                    RB[i] = input[j];
                    break;
                }
            }
            bw.append(RB[i]+" ");

        }

        bw.close();

//        for(int i = 0; i <n; i++) {
//
//            sb.append(RB[i]+" ");
//        }




    }
}

 

하도 모르겠어서.구글을 조금 더 참고해보니... 스텍에 인덱스를 넣어서 푸는 거더라..

아 몰라. 모르겠다고

어떤 사람이 티스토리에 설명으로 과정을 그려서 올려놓은 게 있는데 그걸 봐야 이해가 됨.. 

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

public class RightBig {
    public static void main(String[] args) throws IOException {
        //stack을 이용해 보겠음.
        //스택에 일단 첫번째 인덱스 0을 넣음.
        //반복문으로 스택이 비어있지 않고 스택의 맨 위 인덱스와

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        //수열 A
        int[] input = new int[n];
        //스택
        Stack<Integer> stack = new Stack<>();
        //받은 수열
        String[] str = br.readLine().split(" ");
        //받은 수열 배열에 넣기
        for (int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(str[i]);
        }

        for (int i = 0; i < n; i++) {

            //스텍 비어있지 않고 현재 값이 스텍에서 뽑은 인덱스의 배열값보다 크면
            //그 값을 스텍에서 뽑은 인덱스의 배열값에 넣는다.
            while (!stack.empty()&&(input[i] > input[stack.peek()])) {
                input[stack.pop()] = input[i];
            }
            //현재 값이 더 작거나, 스텍이 비었으면 현재의 인덱스를 스텍에 넣는다.
            stack.push(i);

        }

        //남아있는 인덱스, 즉 오큰수가 없는 인덱스의 값 -1로 바꿔주기
        while(!stack.empty()) {
            input[stack.pop()] = -1;
        }

        for (int i : input) {
            bw.write(i + " ");
        }
        

        bw.close();


    }
}

 

 

 

 

 

---

<결과>

 

참...ㅋ 어휴