백준 17298 오큰수 자바

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

17298번: 오큰수

문제설명

이 문제는 현재 자신의 오른쪽에서 가장 크지만 제일 왼쪽에 있는 숫자를 찾으면 됩니다.

예를 들어 3은 오큰수가 5이고 5는 오큰수가 2는 자신보다 작기 때문에 아니고 7이 됩니다.

 

문제에 대한 아이디어

이 문제를 제일 처음보고 느낀점은 뒤에서 부터 오면서 stack에 숫자를 집어 넣고 현재 자신의 수보다 작은 stack 안의 수는 빼주면 되지 않을까? 였습니다.

예를 들어 3 5 2 6 7이 있다고 해보겠습니다.

• 제일 처음 7을 집어 넣음
• 현재 stack top인 7이 6보다 큼. 6의 오큰수는 7, 6을 집어 넣음
• 오큰수 2는 6
• 오큰수 5는 2가 아님 2를 stack에서 pop 6이 나올 때 까지 pop, 5의 오큰수는 6

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int arr[] = new int[n];
        int answer[] = new int[n];
        answer[n-1] = -1;
        st = new StringTokenizer(buf.readLine());
        for(int i = 0; i < n; ++i){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
        }
        Stack<Integer> stack = new Stack<>();
        stack.add(arr[n-1]);
        for(int i = n-2; i >= 0; --i){
            // 현재 자신보다 stack의 탑이 클 경우
            if(arr[i] < stack.peek()){
                answer[i] = stack.peek();
                stack.add(arr[i]);
            }
            else{
                // stack의 top이 현재 자신보다 클때까지 pop
                while(!stack.isEmpty()){
                    if(arr[i] < stack.peek()) break;
                    stack.pop();
                }
                if(!stack.isEmpty()) answer[i] = stack.peek();
                else answer[i] = -1;
                stack.add(arr[i]);
            }
        }
        for(int i = 0; i < n; ++i){
            Ststem.out.print(answer[i] + " ");
        }
    }
}

 

결과는 시간초과....

그래서 혼자 1시간을 고민하다가 결국 답을 보기로 정했습니다.

 

다른 블로그에서 참고한 코드

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

public class 백준_17298_오큰수 {
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int arr[] = new int[n];
        int answer[] = new int[n];
        Stack<Integer> stack = new Stack<>();
        st = new StringTokenizer(buf.readLine());
        for(int i = 0; i < n; ++i){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
            answer[i] = -1;
        }
        for(int i = 0; i < n; ++i){
           while(!stack.isEmpty() && arr[stack.peek()] < arr[i]){
               answer[stack.peek()] = arr[i];
               stack.pop();
           }
           stack.push(i);
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; ++i){
            sb.append(answer[i]).append(" ");
        }
        System.out.println(sb);
    }
}

Stack의 배열의 수가 아닌 배열의 인덱스를 집어 넣습니다. 그리고 앞에서부터 움직이면서 자신보다 stack의 top인덱스의 수가 현재 배열의 수보다 크다면 stack의 top 인덱스 배열을 수를 현재 배열의 수로 바꿔주면 됩니다.

 

의문점

여기서 생기는 의문 분명 제 코드랑 알고리즘 똑같습니다. for문을 n번돌고 그 안에 while문으로 stack의 수를 빼가면서 하니깐 중복검사도 안합니다. 시간복잡도도 동일합니다. 머가 문제일까 고민해보니 바로 String출력에서 차이가 났습니다...

자바의 string 출력은 System.out.print()로 하나하나씩 출력을 하면 시간이 오래걸립니다. 찾아보니 print는 I/O 작업이며  I/O 시스템콜을 호출하여 커널모드에서 작업합니다. 그러므로 시간이 오래걸릴 수 밖에 없습니다. 그래서 StringBuilder로 모든 문자를 추가해 한번에 출력하면 시간 초과에 걸리지 않습니다.

위의 제 코드를 출력부분만 바꿔서 다시 제출했더니 통과했습니다. 내 소중한 시간이.... 그래도 System.out.println()에 대해 배웠으므로 만족합니다!!!!