글 읽기 - O(n)으로 했는데.. 왜 시간초과가 날까요?

zaza1994 2년 전 0

안녕하세요.

여러번의 실패 끝에 stack을 사용해서 O(n)으로 하셔야한다고 해서 그렇게 구현했습니다.

제가 짠 코드가 O(n)가 아닌건가요..?

왜 1%도 못넘어가고 실패인지 모르겠습니다.

도움 부탁드립니다.

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

public class Main {
	static int N;
	static Stack<Integer> idx;
	static int[] arr, ans;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		idx = new Stack<Integer>();
		arr = new int[N];
		ans = new int[N];
		for(int n = 0; n < N; n++) {
			int num = Integer.parseInt(st.nextToken());
			arr[n] = num;
			while(!idx.isEmpty() &&  num > arr[idx.peek()]) {
				ans[idx.pop()] = num;
			}
			idx.push(n);
		}
		while(!idx.isEmpty()) ans[idx.pop()] = -1;
		for(int i : ans) System.out.print(i + " ");
	}

}

djm03178 2년 전 1

System.out.print는 너무 느립니다. BufferedWriter를 써보세요.

zaza1994 2년 전 0

감사합니다. 덕분에 해결했습니다!

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

문제

문제

출처

ICPC

O(n)으로 했는데.. 왜 시간초과가 날까요?

zaza1994 2년 전 0

djm03178 2년 전 1

zaza1994 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말