글 읽기 - 시간초과 발생하는데 이유를 못 찾겠습니다

brovior 3년 전 0

안녕하세요.

제목 대로 시간초과가 발생하는데 이유를 못찾겠습니다.

실력값을 다 받아온다음에

실력순으로 오름차순 정렬하여 실력값을 순서대로 다시 매겼고,

idx(초기 뛰고 있는 순서)으로 다시 정렬한 펜윅트리에 업뎃하면서 rank(현재 순위 - 내앞에 있는 나보다 못뛰는 주자수)를 매겼습니다.

제 생각에는 N이 50만 이하이므로

1) 73번째 for문에서 발생 : 펜윅트리 50만 x log50만 = 1000만.

2) Arrays.sort에서 발생?

이렇게 추정이 되는데 둘다 1억 미만이라 시간초과가 날거 같지 않은데 이유를 모르겠네요 ㅠ

고수님들께 도움 요청드립니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

	static class Runner {

		int idx;
		int speed;

		public Runner(int idx, int speed) {
			this.idx = idx;
			this.speed = speed;
		}

	}

	static Runner[] Arr;
	static int[] Tree;

	static int N;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		Arr = new Runner[N + 1];
		Tree = new int[N + 1];

		// 초기화
		for (int i = 1; i <= N; i++) {
			Tree[i] = 0;
		}
		
		Arr[0] = new Runner(0,0);
		for (int i = 1; i <= N; i++) {
			Arr[i] = new Runner(i, Integer.parseInt(br.readLine()));
		}

		// 실력순으로 오름차순 정렬
		Arrays.sort(Arr, new Comparator<Runner>() {

			@Override
			public int compare(Runner o1, Runner o2) {				
				return o1.speed - o2.speed;

			}
		});
		
		// 압축
		for(int i = 1; i <=N; i++) {
			Arr[i].speed = i;
		}
		
		// index순으로 오름차순 정렬
		
		Arrays.sort(Arr, new Comparator<Runner>() {
			@Override
			public int compare(Runner o1, Runner o2) {
				return o1.idx - o2.idx;
			}
		});
		
		// 펜윅트리에 값 넣고 (자신의 현재 순위 - 자신보다 앞에 있는데 느린 주자의 명수) 산출 조회하여 출력
        int rank = 0;
		for(int i =1; i <=N; i++) {
			update(Arr[i].speed, 1);
			rank = i - query(Arr[i].speed -1) ;
			bw.write(String.valueOf(rank) + "\n");
			
			
			
		}
		
		bw.flush();
		bw.close();
		br.close();

	}

	// 펜윅 트리 조회
	public static int query(int i) {

		int ret = 0;

		while (i > 0) {
			ret += Tree[i];
			i -= (i & -i);
		}
		return ret;

	}

	//펜윅 트리 update
	public static void update(int i, int val) {

		while (i <= N) {
			Tree[i] += val;
			i += (i & -i);
		}

	}
}

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

문제

문제

출처

ICPC

시간초과 발생하는데 이유를 못 찾겠습니다

brovior 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말